MCOI R4 A solution

简要题解

Part1 预处理子集最大团

定义:f(S)f(S) 是集合 SS 的最大团大小,r(x)r(x) 是点 xx 的邻居的集合

对于任意一个 SS\neq \varnothing,取任意 xSx\in S,考虑 xx 是否在最大团中,可以得到转移:f(S)=max(1+f(Sr(x)),f(S{x}))f(S)=\max(1+f(S\cap r(x)),f(S-\{x\}))

状压从小到大枚举 SS,dp 计算即可

注意到我们只需要对每个子集大小分别求出子集最大团的和

所以数组可以开大小 2n12^{n-1}char类型,因为后 2n12^{n-1} 个值不会再次被用到了

Part2 计算贡献

如果在第 yy 回合结束后剩下一个大小为 xx 的子集,包含这种状态的方案数应该是 ynx((ky+1)x(ky)x)y^{n-x}((k-y+1)^x-(k-y)^x)

也就是,考虑每个点是在哪一回合删除的

由于 xx 的范围只有 [0,n][0,n] 所以可以枚举,所以要求的就是 y=1kynx((ky+1)x(ky)x)\sum_{y=1}^k y^{n-x}((k-y+1)^x-(k-y)^x)

这是个关于 kkn+1n+1 次多项式,暴力求 n+2n+2 个点值然后拉格朗日插值即可

Part3 卡常

这个……看标程吧,最大点 356ms,还挺快的(初代标程最大点 700+ms,
被我优化了一半常数,我认为有必要区分一下)

标程长这样,欢迎抄题解

#include <cstdio>
#include <algorithm>
#define N 28
#define P 1000000007
int n, m, k, G[N], s[N+1]; char a[1<<(N-1)];
int inv[N+2], pow[N+2][N+1];
int main() {
	scanf("%d%d%d", &n, &m, &k);
	while (m--) {
		int x, y;
		scanf("%d%d", &x, &y);
		G[x] |= 1 << y;
		G[y] |= 1 << x;
	}
	for (int x = 1, t = 1, d = 0; ; x++) {
		if (x & (t<<1)) {t <<= 1; if (++d == n-1) break; }
		a[x] = std::max(a[x^t], char(a[x&G[d]]+1));
		int c = __builtin_popcount(x); s[c] += a[x];
		s[c+1] += std::max(int(a[x]), a[x&G[n-1]]+1);
	}
	s[1]++;
	pow[0][0] = inv[1] = 1;
	for (int i = 1; i <= n+1; i++) {
		pow[i][0] = 1;
		for (int j = 1; j <= n; j++)
			pow[i][j] = 1ll * pow[i][j-1] * i % P;
	}
	for (int i = 2; i <= n+1; i++)
		inv[i] = 1ll * (P-P/i) * inv[P%i] % P;
	int ans = 0;
	for (int g = 1; g <= n; g++) {
		for (int i = 1; i <= n+1; i++) {
			int y = 0;
			for (int j = 1; j <= i; j++)
				y = (1ll * pow[j][n-g] * (pow[i-j+1][g] - pow[i-j][g] + P) + y) % P;
			for (int j = 0; j <= n+1; j++) if (i != j)
				y = 1ll * y * (k-j+P) % P * (i>j?inv[i-j]:P-inv[j-i]) % P;
			ans = (1ll * y * s[g] + ans) % P;
		}
	}
	printf("%d\n", ans);
}