AGC022F - Checkers
考虑一次操作，相当于选出两个数a,b，合并为2a-b，求最后数字的方案数。
于是初始每个数对最后的数的贡献一定是\((-1)^{c_i}2^{d_i}\)，其中\(c_i\)为\(0,1\)。
由于\(a_k=10^{100k}\)，所以一定不会存在两组不同的\(c_i,d_i\)使得\(\sum{a_i(-1)^{c_i}2^{d_i}}\)相等。
于是就只要考虑有多少组不同的\(c,d\).
考虑把合并方案表示为一个类似于重构树的东西。
每次合并两个数\(a,b\)，就用一个新点作新根，\(a\)是它的右子树，\(b\)是它的左子树。
那么最后每个数的\(c_i\)就是表示它的叶子到根的路经上是左儿子的点奇偶性，\(d_i\)就是是右儿子的点的奇偶性。
就会得到一个二叉树。
考虑二叉树转成多叉树。
如果把每个非叶子点和它的左子树根合并成一个点，就会得到一个多叉树。
此时每个子树都是原树的一个子树，子树根就是对应子树左链底，根的每个孩子就是链上每个点的右儿子。
此时每个点都对应一个数，到根的路经就是\(d_i\)。
给每个子树一个「树权」，代表这个子树在原树中子树根的\((-1)^{c_i}\)。
每个点还有个点权，就是这个点在原树中的\((-1)^{c_i}\)。
假设以\(x\)为根的子树树权为\(1\)。如果\(x\)点权为\(1\)，那么\(x\)一定有偶数个孩子，恰好有一半树权是\(1\)，另一半是\(-1\)。
否则\(x\)点权为\(-1\)，\(x\)一定有奇数个儿子，\(\lceil\frac{s}{2}\rceil\)个为\(1\)，\(\lfloor\frac{s}{2}\rfloor\)个为\(-1\)
树权为\(-1\)全部取反即可。
考虑计算答案。记\(f_{n,a,b}\)表示有\(n\)个点，最后一层有\(a\)个点，且树权有\(b\)个为\(1\)的方案数。
枚举有\(x\)个树权为\(1\)的点点权取反，有\(y\)个为\(-1\)的点点权取反。
如果有一个\(1\)取反，那么下一层\(1\)要比\(-1\)多一个，\(-1\)也类似。
如果对同一层一个\(1\)点权取反，同时对一个\(-1\)点权取反，那么不会对\(1\)和\(-1\)的大小关系产生影响，也不会对这一层\(1,-1\)个数产生影响，没有必要。
于是只用考虑\(x=0\)或\(y=0\)的情况。
压缩代码长度之后的代码：
#include<iostream>
#define int long long
#define F(a,b,c) for(int a=b;a<=c;++a)
const int p=1e9+7;
int f[55][55][55],c[55][55];
signed main(){
int n;
std::cin>>n;
f[1][1][1]=1;
F(i,0,n){
c[i][0]=c[i][i]=1;
F(j,1,i-1)c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
}
F(i,1,n-1)F(j,1,i)F(k,0,j)F(l,0,j)F(w,(k-l>0?k-l:0),(n-i+k-l)>>1)
if(w+l-k+w>0)(f[w+l-k+w+i][w+l-k+w][w]+=f[i][j][k]*c[j][l]%p*c[w+l-k+w+i][i])%=p;
int ans=0;
F(i,1,n)F(j,0,i)ans=(ans+f[n][i][j]*c[i][j])%p;
std::cout<<ans;
return 0;
}