2020“图灵杯”趣味网络邀请赛 C. 染色（推式子+组合数）

2020“图灵杯”趣味网络邀请赛 C. 染色

题解

• 有一个很简单的想法，两种颜色的个数，设他们分别为 A , B A,B A,B，则第三种的个数为 C = n − A − B C=n-A-B C=n−A−B，则答案为 ∑ A = 0 n ∑ B = 0 n − A ( n A ) ∗ ( n − A B ) ∗ 2 A ∗ B + ( A + B ) ∗ ( n − A − B ) \sum_{A=0}^n\sum_{B=0}^{n-A}{n\choose A}*{n-A\choose B}*2^{A*B+(A+B)*(n-A-B)} ∑A=0n​∑B=0n−A​(An​)∗(Bn−A​)∗2A∗B+(A+B)∗(n−A−B)，复杂度为 O ( t n 2 ) O(tn^2) O(tn2)，还需考虑优化。
• 可以先枚举 A A A，则剩下的 B + C B+C B+C固定，在询问前先预处理号 B + C = s B+C=s B+C=s时的答案方案数 f s f_s fs​，则答案为 ( n A ) ∗ f n − A ∗ 2 A ∗ ( n − A ) {n\choose A}*f_{n-A}*2^{A*(n-A)} (An​)∗fn−A​∗2A∗(n−A)。
• f s f_s fs​的计算只需枚举 B B B是多少，则 f s = ∑ B = 0 s ( s B ) ∗ 2 B ∗ ( s − B ) f_s=\sum_{B=0}^s{s\choose B}*2^{B*(s-B)} fs​=∑B=0s​(Bs​)∗2B∗(s−B)。
• 这样一来，复杂度降为 O ( n 2 + t n ) O(n^2+tn) O(n2+tn)，可以通过。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long
#define ld long double
#define N 2010
ll e[N * N], c[N][N], ans[N], f[N];
ll read() {
	ll s = 0;
	char x = getchar();
	while(x < '0' || x > '9') x = getchar();
	while(x >= '0' && x <= '9') s = s * 10 + x - 48, x = getchar();
	return s;
}
int main() {
	int tn = read(), p = read(), i, j, k;
	e[0] = 1;
	for(int i = 1; i < N * N; i++) e[i] = e[i - 1] * 2 % p;
	for(i = 0; i < N; i++)  {
		c[i][0] = c[i][i] = 1;
		for(j = 1; j < i; j++) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % p;
	}
	for(i = 0; i < N; i++) {
		for(j = 0; j <= i; j++) f[i] = (f[i] + e[j * (i - j)] * c[i][j]) % p;
	}
	while(tn--) {
		int n = read();
		ans[n] = 0;
		for(i = 0; i <= n; i++)  {
			ll t = c[n][i];
			ans[n] = (ans[n] + t * f[n - i] % p * e[i * (n - i)]) % p;
		}
		printf("%lld\n", ans[n] % p);
	}
	return 0;
}