AGC022F - Checkers

题目链接
最近做的最神仙的一道DP/计数题。
原本的想法是A关于B对称，就新建一个点C，A向这个点连一条-1的边，B连2的边，这样两种方案不同当且仅当存在一个点到根路径的乘积不同，但这样要同时关心2,-1的个数，难以计数。
发现乘积只跟-1的奇偶性有关，先考虑2的边，把-1的边缩起来，直接把A放到C上，这样就相当于B连向A，把A取反，于是问题变为计算这样的n个点的有标号的树的个数，两棵树不同当且仅当有一个点的深度或正负号不同。
发现正负号的问题比较麻烦，一个点会被所有儿子取反一次，然后被所有祖先的儿子取反一次。可以直接利用父亲的正负来推出儿子，但如果直接记录当前层有多少个正、负点的话，效率难以优化过$O(n^5)$。
但发现两颗仅存在正负号不同的点的树，将点与父亲做差分（即相同为1，不同为-1）后也不同，反之亦然。于是直接记录当前层差分为-1的点的个数，枚举下一层差分为-1,1的点数（不考虑下一层的儿子影响），可计算出下一层差分为-1的点数（考虑下一层的儿子影响，这里直接把所有的差距由1改为-1或-1改为1，因为同时把1改为-1且把1改为-1会被其它不同时改的方案记录到），效率为$O(n^4)$。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll P=1e9+7;
const int N=55;
int n; ll c[N][N],f[N][N];
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n; c[0][0]=1;
	for(int i=1;i<=n;i++){
		c[i][0]=1;
		for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%P;
	}
	f[1][0]=f[1][1]=n;
	for(int i=1;i<n;i++) for(int j=0;j<=i;j++){
		//printf("i=%d j=%d f=%lldn",i,j,f[i][j]);
		for(int x=0;x<=n-i;x++) for(int y=0;x+y<=n-i;y++) if(x+y>=max(j,1) && !((x+y-j)&1)){
			(f[i+x+y][abs(j+(x+y-j)/2-x)]+=f[i][j]*c[n-i][x+y]%P*c[x+y][x])%=P;
			//cout<<x<<" "<<y<<" "<<abs(j+(x+y-j)/2-x)<<endl;
		}
	}
	cout<<f[n][0]<<endl;
	return 0;
}

最后

以上就是要减肥早晨为你收集整理的AGC022F - Checkers的全部内容，希望文章能够帮你解决AGC022F - Checkers所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。