目录
- 比赛链接
- 总结
- 知识点
- 易错点
- 题解
- J - 瑞士轮
- D - Devil May Cry
比赛链接
link to contest
总结
知识点
D - Devil May Cry
- 子集卷积的 FMT 优化技巧
易错点
E - 睡觉
- 写代码，特别是“大讨论”的时候，适当慢一点
正在比较文件 a.cpp 和 B.CPP
***** a.cpp
inline bool check() {if(sum < 0) return 1;***** B.CPP
inline bool check() {if(sum < 0) return 0;*****
题解
J - 瑞士轮
有如下观察：
- 比赛两轮之后决出 2-0 和 0-2 的队伍，再进行一轮之后决出所有 2-1 和 1-2 的队伍
- 编号每四个为一组，则所有的比赛都发生在组内
则，对于每一组算出各种情况的概率，再计算其对询问的贡献即可。
int main(){for(int i=0; i<n;++i) cin>>a[i];for(int i=0; i<n; i+=4) {int p[4][4];for(int x=0; x<4; ++x)for(int y=0; y<4; ++y)if(x!=y) p[x][y] = 1ll * a[i+x] * Pow((a[i+x]+ a[i+y]) % mod, mod-2) % mod;else p[x][y] = 0;for(int S=0; S<(1<<5); ++S) {int d[4] = {0, 1, 2, 3};int prob = 1;if(S&1) prob = 1ll * p[d[0]][d[1]] * prob % mod;else prob = 1ll * p[d[1]][d[0]] * prob % mod, swap(d[0], d[1]);if(S&2) prob = 1ll * p[d[2]][d[3]] * prob % mod;else prob = 1ll * p[d[3]][d[2]] * prob % mod, swap(d[2], d[3]);if(S&4) prob = 1ll * p[d[0]][d[2]] * prob % mod;else prob = 1ll * p[d[2]][d[0]] * prob % mod, swap(d[2], d[0]);if(S&8) prob = 1ll * p[d[1]][d[3]] * prob % mod;else prob = 1ll * p[d[3]][d[1]] * prob % mod, swap(d[1], d[3]);if(S&16) prob = 1ll * p[d[1]][d[2]] * prob % mod;else prob = 1ll * p[d[2]][d[1]] * prob % mod, swap(d[1], d[2]);for(int j=0; j<4; ++j) {f[d[j] + i][j] = (f[d[j] + i][j] + prob) % mod;// cout << d[j] + i << ' ';}}} int q;read(q);while(q--){int x;read(x); --x;LL ans=0;ans=(ans+f[x][0])%Mod;read(x); --x;ans=(ans+f[x][3])%Mod;for(int i=1;i<=7;++i){read(x); --x;ans=(ans+f[x][1]+f[x][0])%Mod;}printf("%lld\n", ans);}return 0;
}
D - Devil May Cry
- 本题做法与 P6570 相似
- 利用子集卷积的思想，转化为对每个 \(S, j\)，求“所有的技能的出现位置都是 \(S\) 的子集，出现位置的总个数为 \(j\)” 的方案数（不要求不同技能的出现位置不重合）；然后枚举定 \(S\)，变成经典的数数问题
- 固定 \(S\) 的时候，我们需要求的生成函数为
\[\prod_{i = 1}^m \left(\sum_{P \subseteq S \cap T_i} \left[|P| \le lim_i\right]x^{|P|}\right)\\
= \prod_{i=1}^m \left(\sum_{j=0}^{lim_i }\binom{|S \cap T_i|}{j} \cdot x^j\right)
\]
- 这里 \(T_i\) 表示第 \(i\) 种技能允许出现的位置集合，\(lim_i\) 表示第 \(i\) 种技能允许出现的次数上限
- 考虑用多项式 ln, exp 的技巧计算累乘。注意到每个累乘项只与 \(\lim_i, |S \cap T_i|\) 有关，这两者都不超过 \(n\)，所以至多有 \(n^2\) 种本质不同的累乘项。对每种累乘项暴力计算对数，再相加算指数即可。
- 这里的多项式指数、对数的操作都是 \(O(n^2)\) 暴力做的：
- \(\ln F = \frac{F'}{F}\)
- 当 \(F = e^{H}\)，有 \(F = \int H' F dx\)
- 总时间复杂度 \(O\left(n^4 + 2^n \cdot \left(nm + n^2\right)\right)\)
const int N = 20;
const int M = 200 + 5;
const int mod = 998244353;inline int Pow(int x, int y) {int res = 1;for(;y;y>>=1, x=1LL*x*x%mod)if(y&1) res=1LL*res*x%mod;return res;
}int bitcnt[1<<N];
int T[M], lim[M];
int n, m;int f[1<<N][N + 2];
int g[N + 2][N + 2];
int h[N + 2][N + 2][N + 2]; // 相应的 ln 的结果int C[N + 2][N + 2], invnum[N + 2];void calc_binomial(int n) {for(int i=0; i<=n; ++i) {C[i][0] = 1;for(int j=1; j<=i; ++j) {C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;}}for(int i=1; i<=n; ++i) invnum[i] = Pow(i, mod - 2);
}void calcln(int cnt, int lim, int res[N + 2]) {static int F[N + 2], G[N + 2], H[N + 2];for(int j = 0; j <= lim; ++ j)F[j] = C[cnt][j];for(int j=lim + 1; j <= n; ++j)F[j] = 0;// 求 G = 1 / F，已知 F_0 = 1// 递推式：当j>1，[x^j] F(x)G(x) = (f_0g_j + f_1g_{j-1} + ... + f_jg_0) = 0G[0] = 1;for(int j = 1; j <= n; ++ j) {G[j] = 0;for(int k = 1; k <= j; ++ k) {G[j] = (G[j] + mod - 1LL * F[k] * G[j - k] % mod) % mod;}// G[j] = 1LL * G[j] * Pow(F[0], mod - 2) % mod;}// 求 H = F' * Gfor(int j = 0; j <= n; ++ j) {H[j] = 0;for(int k = 0; k <= j; ++ k) {H[j] = (H[j] + 1LL * (k + 1) * F[k + 1] % mod * G[j - k] % mod) % mod;}}// 求 res = int Hres[0] = 0;for(int j = 1; j <= n; ++ j) {res[j] = 1LL * H[j - 1] * invnum[j] % mod;}
}void calc_exp(int h[N + 2], int n) {static int f[N + 2];f[0] = 1;for(int i=1; i<=n; ++i) {f[i] = 0;for(int j=0; j<=i-1; ++j) {f[i] = (f[i] + 1ll * f[j] * h[i - j] % mod * (i - j) % mod) % mod;}f[i] = 1ll * f[i] * invnum[i] % mod;}for(int i=0; i<=n; ++i) h[i] = f[i];
}int main() {rd(n), rd(m);for(int i=1; i<=m; ++i) {rd(lim[i]);}// lim[i]: 技能 i 最多能出现的次数for(int i=1; i<=m; ++i) T[i] = ((1<<n) - 1);int tt; rd(tt);while(tt--) {int x, y; rd(x), rd(y);T[y] &= ~(1<<x-1);}// T[y]: 技能 y 可以出现的位置集合int full = (1<<n) - 1;for(int i=1; i<=full; ++i) bitcnt[i] = bitcnt[i>>1] + (i&1);calc_binomial(n);for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j)calcln(i, j, h[i][j]);for(int S = 0; S<=full; ++S) {for(int i=1; i<=m; ++i) {int p = bitcnt[S & T[i]];int q = lim[i];for(int k=0; k<=n; ++k)f[S][k] = (f[S][k] + h[p][q][k]) % mod;}calc_exp(f[S], n);}// IFMT f[][n]for(int k=1; k<=n; ++k) {for(int S=0; S<=full; ++S) if(S >> k-1 & 1) {f[S][n] = (f[S][n] - f[S^(1<<k-1)][n]) % mod;}}int ans = f[full][n];ans = (ans % mod + mod) % mod;print(ans), puts("");return 0;
}