欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-18 23:25:58
...

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

题解

  • 有一个很简单的想法,两种颜色的个数,设他们分别为 A , B A,B A,B,则第三种的个数为 C = n − A − B C=n-A-B C=nAB,则答案为 ∑ 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=0nB=0nA(An)(BnA)2AB+(A+B)(nAB),复杂度为 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)fnA2A(nA)
  • 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(sB)
  • 这样一来,复杂度降为 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;
}