题目
洛谷翻译：https://www.luogu.com.cn/problem/AT3951
正解
诡异DP……
当(A)和(B)变成(2A-B)的时候，就让(A)当(B)的父亲。最终会形成一棵带儿子相对顺序的树。
一个点的贡献可以视作(2^{d_i}c_ix_i)的形式，其中(x_i)太大，所以直接将其当成未知数考虑。
(d_i)表示节点的深度。(c_i)为正负号。
接下来考虑怎么求出(c_i)：按深度优先顺序加点，加点前将父亲的子树中所有点的(c_i)取反。
这样子考虑太麻烦，不如换种方式考虑：按照深度优先顺序计算，对于某个点(x)，看(y)是(x)的从右往左数第几个儿子，如果是(x)的第偶数个儿子，则(c_y)取(-c_x)，否则取(c_x)。
搞完之后，对于每个点，统计它的儿子的个数，如果为奇数则取反。
我们要计算不同的方案数，只需要保证存在(d_i)或(c_i)不同。
DP解决。首先(d_i)用按层转移的方式来搞定。按层转移的时候，已经确定了前面这些层最终的(c_i)，这样最后一层有奇数个儿子的点数是可以记录的（奇数个儿子可以修正(c_i)）。
(f_{i,j})表示已经放了(i)个节点，最后一层有(j)个节点的儿子的个数为奇数，此时的方案数。
转移考虑当前这层“长出”了一些节点。
为了方便计算将(c_i)差分，如果和父亲相同记作(1)否则记作(-1)。接下来只关心下一层的点有多少个和父亲相同，多少个和父亲不同。
（正确性？。。。。。。）
如果一个点有(k)个儿子，那么其中(lfloor frac{k}{2} floor)个儿子的(c_i)和它不同（先忽略儿子的儿子对儿子颜色的影响）。
现在设下一层长出了(k)个节点，有(frac{k-j}{2})个点是和父亲不同的。（注意不是整除）
设经过儿子的儿子调整之后，真正的和父亲不同的个数有(x)个。于是有(|x-frac{k-j}{2}|)个节点的(c_i)需要修正，即这就是下一层儿子个数为奇数的节点数。
注意这里只转移到(|x-frac{k-j}{2}|)。虽然变成(|x-frac{k-j}{2}|+2z,zin N)也是合法的，但是这样就会同时存在“不同”修正为“相同”和“相同”修正为“不同”，这时候就会出现算重的情况。
时间复杂度就是(O(n^4))的了。
代码
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 55
#define mo 1000000007
#define ll long long
int n;
ll C[N][N],f[N][N];
int main(){
scanf("%d",&n);
for (int i=0;i<=n;++i){
C[i][0]=1;
for (int j=1;j<=i;++j)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo;
}
f[1][0]=f[1][1]=n;
for (int i=1;i<n;++i)
for (int j=0;j<=i;++j)
for (int k=(j==0?2:j);i+k<=n;k+=2){
int t=(k-j)/2;
for (int x=0;x<=k;++x)
(f[i+k][abs(x-t)]+=f[i][j]*C[n-i][k]%mo*C[k][x])%=mo;
}
printf("%lld
",f[n][0]);
return 0;
}