[AGC022F]Checkers

Description

令$x=10^{100}$，数轴上有n个点，第i个点的坐标为$x^i$
进行n-1次操作，第i次操作选择两个点A和B，将A变为A关于B的对称点，然后删去B
最后会剩下1一个数，问这个数有多少种可能的取值
n<=50

Solution

由于x很大，我们可以只考虑每个数的贡献
容易知道每个数的贡献形式为±2^k
如果我们选择A和B，就从B向A连一条边，最后我们会得到一棵有根树，第i个点的权值为2^深度
现在考虑正负号，首先一个点的每个儿子都会将其取反一次
然后每个点的所有祖先在这个点之后选择的其他儿子也会将这个点取反一次
我们直接考虑某个点是否等于父亲，那么只需要考虑父亲的其他儿子的贡献和自己的儿子数
若一个点有k个儿子，那么会有$\lfloor \frac{k}{2}\rfloor$个点和其状态不同
考虑一层一层转移，我们需要知道上一层有j个点有奇数个儿子
枚举这一层有k个点，不考虑这一层点的儿子的影响，我们会有(k-j)/2个点和父亲不同
枚举实际有x个点和父亲不同，我们需要令$|\frac{(k-j)}{2}-x|$个点有奇数个儿子
直接转移即可，复杂度是O(n^4)的

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long ll;

const int N=55,Mo=1e9+7;

int n,C[N][N],f[N][N];

void inc(int &x,int y) { 
   x=x+y>=Mo?x+y-Mo:x+y;}

int main() { 
   
	scanf("%d",&n);
	fo(i,0,n) { 
   
		C[i][0]=1;
		fo(j,1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mo;
	}
	f[1][0]=f[1][1]=n;
	fo(i,1,n-1)
		fo(j,0,i)
			fo(k,max(j,1),n-i) { 
   
				if ((k-j)&1) continue;
				int y=(k-j)/2;// 当前和父亲不一样
				fo(x,0,k) { 
   
					// 目标和父亲不一样
					inc(f[i+k][abs(y-x)],(ll)f[i][j]*C[n-i][k]%Mo*C[k][x]%Mo);
				}
			}
	printf("%d\n",f[n][0]);
	return 0;
}

今天的文章[AGC022F]Checkers分享到此就结束了，感谢您的阅读。