心路歷程 預計得分：$30 + 0 + 0 = 30$ 實際得分：$0+0+0= 0$ T1算概率的時候沒模爆long long了。。。 A 我敢打賭這不是noip難度。。。 考慮算一個位置的概率，若想要$k$步把它幹掉，那麼與他距離為$1$到$k - 1$的點都必須阻塞 且距離為$k$的點至少有一 ...
心路歷程
預計得分：$30 + 0 + 0 = 30$
實際得分：$0+0+0= 0$
T1算概率的時候沒模爆long long了。。。
A
我敢打賭這不是noip難度。。。
考慮算一個位置的概率，若想要$k$步把它幹掉，那麼與他距離為$1$到$k - 1$的點都必須阻塞
且距離為$k$的點至少有一個沒被阻塞
概率的處理可以用首碼和優化。
這樣看似是$O(n^3 logn)$，但是卻不能通過，考慮在首碼和處理的時候有很多沒用的狀態(超出邊界)
加一些剪枝即可
#include<cstdio> #define max(a, b) (a < b ? b : a) #define LL long long using 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; }A
B
考場上根本就沒時間做。。
題目給出的模型太難處理了，考慮轉化成一個較為普通的模型
遇到這種每個點有兩個狀態的題不難想到拆點，分別表示贏 / 輸
當$a$贏了$b$，就從$a$贏向$b$輸連邊。
這樣會得到一個新的無環圖，可以證明，兩個圖中的環是等價的。
直接暴力找最小環即可，時間複雜度：$O(n^2 T)$
#include<bits/stdc++.h> using namespace std; const int MAXN = 10005, BIT = 13; int N, M, dep[MAXN], fa[MAXN][21], MC, U, V; vector<int> 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<int> 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<int> 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; } /* */B
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<bits/stdc++.h> #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; } /* 1 2 21 */C
