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;
}