心路历程

预计得分：$30 + 0 + 0 = 30$

实际得分：$0+0+0= 0$

T1算概率的时候没模爆long long了。。。

A

我敢打赌这不是noip难度。。。

考虑算一个位置的概率，若想要$k$步把它干掉，那么与他距离为$1$到$k - 1$的点都必须阻塞

且距离为$k$的点至少有一个没被阻塞

概率的处理可以用前缀和优化。

这样看似是$O(n^3 logn)$，但是却不能通过，考虑在前缀和处理的时候有很多没用的状态(超出边界)

加一些剪枝即可

#include
      
       #define max(a, b) (a < b ? b : a)#define LL long longusing namespace std;const int MAXN = 201, mod = 1e9 + 7, INF = 1e9 + 10;inline int read() {    char c = getchar(); int x = 0, f = 1;    while(c < '0' || c > '9') {
    if(c == '-') f = -1; c = getchar();}    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();    return x * f;}int N, M, a[MAXN][MAXN], g[MAXN][MAXN][MAXN], vis[MAXN][MAXN];LL fastpow(LL a, LL p) {    LL base = 1;    while(p) {        if(p & 1) base = 1ll * base * a % mod;        a = 1ll * a * a % mod; p >>= 1;    }    return base;}LL inv(LL a) {    return fastpow(a, mod - 2);}int mul(int a, int b) {    if(1ll * a * b > mod) return 1ll * a * b % mod;    else return a * b;}void Pre() {    //cout << a[1][1] << endl;    for(int i = 1; i <= N; i++)        for(int j = 1; j <= M; j++)            g[0][i][j] = a[i][j] % mod;     for(int k = 1; k <= max(N, M); k++)        for(int i = 1; i <= N; i++)            for(int j = 1; j <= M; j++) {                if((i - k < 0) || (j - k < 0) || (i + k > N + 1) || (j + k > M + 1)) {vis[i][j] = 1; continue;}                if(vis[i][j]) continue;                g[k][i][j] = mul(g[k - 1][i - 1][j], g[k - 1][i + 1][j]);                if(k > 2) g[k][i][j] = mul(g[k][i][j], inv(g[k - 2][i][j]));                if(k >= 2) g[k][i][j] = mul(mul(g[k][i][j], inv(a[i][j + k - 2])), inv(a[i][j - k + 2]));                g[k][i][j] = mul(mul(g[k][i][j], a[i][j + k]), a[i][j - k]);            }}LL calc(int x, int y) {    LL ans = 0, s = a[x][y];    for(int i = 1; i <= max(N, M); i++) {        if((x - i < 0) || (y - i < 0) || (x + i > N + 1) || (y + i > M + 1)) break;        int now = g[i][x][y];        ans = (ans + mul(mul(i, (1 - now + mod)), s)) % mod;        s = mul(s, now);    }    return ans;}int main() {//  freopen("a.in", "r", stdin);    N = read(); M = read();    for(LL i = 1; i <= N; i++) {        for(LL j = 1; j <= M; j++) {            LL x = read(), y = read();            a[i][j] = mul(x, inv(y));        }    }    Pre();    for(LL i = 1; i <= N; i++, puts(""))        for(LL j = 1; j <= M; j++)            printf("%lld ", calc(i, j) % mod);    return 0;}
      

 

B

考场上根本就没时间做。。

题目给出的模型太难处理了，考虑转化成一个较为普通的模型

遇到这种每个点有两个状态的题不难想到拆点，分别表示赢 / 输

当$a$赢了$b$，就从$a$赢向$b$输连边。

这样会得到一个新的无环图，可以证明，两个图中的环是等价的。

直接暴力找最小环即可，时间复杂度：$O(n^2 T)$

#include
      
       using namespace std;const int MAXN = 10005, BIT = 13;int N, M, dep[MAXN], fa[MAXN][21], MC, U, V;vector
       
         v[MAXN];int LCA(int x, int y) {    if(dep[x] < dep[y]) swap(x, y);    for(int i = BIT; i >= 0; i--) if(dep[fa[x][i]] >= dep[y]) x = fa[x][i];    if(x == y) return x;    for(int i = BIT; i >= 0; i--) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];    return fa[x][0];}void bfs(int x) {    queue
        
          q;    q.push(x); dep[x] = 1; fa[x][0] = 0;    while(!q.empty()) {        int p = q.front(); q.pop();        for(int i = 0, to; i < v[p].size(); i++) {            if(!dep[to = v[p][i]]) {                fa[to][0] = p; dep[to] = dep[p] + 1;                for(int j = 1; j <= BIT; j++) fa[to][j] = fa[fa[to][j - 1]][j - 1];                q.push(to);            }            else if(to != fa[p][0]) {                int lca = LCA(p, to), dis = dep[p] + dep[to] - 2 * dep[lca] + 1;                if(dis < MC) MC = dis, U = p, V = to;            }        }    }}int main() {    int meiyong; scanf("%d", &meiyong);    while(scanf("%d", &N) && N) {
    //tag        scanf("%d", &M);                   MC = MAXN;        for(int i = 1; i <= 2 * N; i++) v[i].clear();        memset(dep, 0, sizeof(dep));        memset(fa, 0, sizeof(fa));                   for(int i = 1; i <= M; i++) {            int x, y; scanf("%d %d", &x, &y);            v[x].push_back(y + N); v[y + N].push_back(x);        }                   for(int i = 1; i <= 2 * N; i++) if(!dep[i]) bfs(i);        if(MC == MAXN) {puts("-1");continue;}        int lca = LCA(U, V);        vector
         
           ans; ans.clear();        printf("%d\n", MC);        while(U != lca) printf("%d ", (U - 1) % N + 1), U = fa[U][0];        printf("%d", (lca - 1) % N + 1);        while(V != lca) ans.push_back((V - 1) % N + 1), V = fa[V][0];        for(int i = ans.size() - 1; i >= 0; i--) printf(" %d", ans[i]);        puts("");    }    return 0;}/**/
         
        
       
      

C

$k=2$的时候是

$k \not = 2$的时候是神仙结论

考虑$k \not = 2$怎么做。

结论：

若$l = n$时先手必输，那么我们找到一个$m = \frac{n}{k} >= n$，且最小的$m$，当$l = n+m$先手也一定必输

证明：

我们把多着的$m$个单独考虑，若$n < l < n+m$时，先手拿走多余的$m$个，后手必败。

但当$l = n +m$时，先手不能拿走$m$个，因为此时后手可以一步拿走剩余的。

不断往下推就行了

#include
      
       #define LL long long  using namespace std;const int MAXN = 1e7 + 10;int T, k, top;LL l, sta[MAXN];int main() {    cin >> T;    while(T--) {        cin >> k >> l;        LL now = 1;        sta[top = 1] = 1;        while(now < l) {            int nxt = lower_bound(sta + 1, sta + top + 1, (now % k == 0) ? now / k : (now / k + 1)) - sta;            sta[++top] = (now = (now + sta[nxt]));        }        puts(now == l ? "DOG" : "GOD");    }    return 0;}/*12 21*/