题目链接
题目解法
很妙的题！！！
考虑 \(x\) 是无穷大的数，所以可以认为 \(x^i\) 的系数是单独的一项，不会和 \(x^j(j\neq i)\) 合并
所以问题转化成了：每个数初始是 \(x^i\)（\(x\) 可以理解是元），进行题目中的操作，问最后形成的 \(n\) 次多项式的个数
由 \(B\) 向 \(A\) 连边，这会形成一棵树
考虑 \(x^i\) 的系数，手画一下可以发现为 \(c\times 2^{depth_i},\;c\in\{1,-1\}\)
我们用递推的方式考虑 \(c_i\) 的值
如果 \(c_{fa_i}\) 是已知的，每个儿子会使 \(c_i\times (-1)\)，所以 \(c_i=c_{fa_i}\times (-1)^{cntson(i)}\)
所以 \(c_i\) 与 \(c_{fa_i}\) 不同只与 \(i\) 儿子的奇偶性有关，也就是说，通过 \(c_i\) 和 \(c_{fa_i}\) 是否相同以及每个节点的深度可以确定一个多项式
考虑一个 \(dp\)，令 \(f_{i,j}\) 为前若干层共有 \(i\) 个点，当前层有 \(j\) 个点的儿子数量为奇数
枚举下一层的节点个数 \(k(k\ge j)\)
那么不考虑儿子数量的奇偶性，下一层节点中和父亲 \(c\) 相同的个数为 \(t=\frac{k-j}{2}\)，需要保证 \(2|k-j\)
枚举下一层实际和父亲 \(c\) 相同的个数 \(p\)，自己手画一下图可以发现，下一层中度数为奇数的节点的个数 \(\ge |t-p|\)
这里给出一个结论：只需要从 \(f_{i,j}\) 转移到 \(f_{i+k,|t-p|}\)，不能转移到 \(f_{i+k,|t-p|+2w}\)
为什么？第一，根据递推式，我们只关心下一层中实际和父亲相同的点的个数，而不在乎树的形态（就是怎么连，不包括节点深度），而 \(f_{i+k,|t-p|}\) 可以转移到所有 \(f_{i+k,|t-p|+2w}\) 的点，当然是取 \(w=0\)；第二，\(luogu\) 题解区有 \(hack\) 图
所以转移为：\(f_{i+k,|t-p|}\Leftarrow f_{i,j}\binom{n-i}{k}\binom{k}{p}\)
边界为 \(f_{1,0}=f_{1,1}=1\)，答案为 \(f_{n,0}\)
时间复杂度 \(O(n^4)\)
点击查看代码
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int N=55,P=1e9+7;
int n,f[N][N],C[N][N];
//f[i][j]：有i个点，当前层有j个点儿子个数为奇数的方案数
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
int main(){
n=read();
C[0][0]=1;
F(i,1,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[1][0]=f[1][1]=n;
F(i,1,n) F(j,0,i) if(f[i][j])
F(k,max(1,j),n-i){//下一层有k个点
if((k-j)&1) continue;
int t=(k-j)/2;//不考虑儿子个数的奇偶性，下一层有t个点和父亲符号相同
F(p,0,k) inc(f[i+k][abs(t-p)],1ll*f[i][j]*C[n-i][k]%P*C[k][p]%P);//下一层实际有p个点和父亲符号相同
}
printf("%d\n",f[n][0]);
return 0;
}
能不能再给力一点
我们拆开转移式：\(f_{i,j}\binom{n-i}{k}\binom{k}{p}=f_{i,j}\frac{(n-i)!}{(n-i-k)!p!(k-p)!}\)
接下来的一步比较妙，令 \(x=p,\;y=k-p\)
那么 \(f_{i+x+y,\frac{|y-x-j|}{2}}=f_{i,j}(n-i)!\times \frac{1}{(n-i-x-y)!x!y!}\)
这里重新定义 \(f_{i,j}\) 为 \(f_{i,j}(n-i)!\)
所以 \(f_{i+x+y,\frac{|y-x-j|}{2}}=f_{i,j}\frac{1}{x!y!}\)
可以发现，\(x,y\) 关系不大，考虑拆开 \(x,y\)
这里给出转移式：
\(\left\{
\begin{aligned}
g_{i+y,y-j}=f_{i,j}\frac{1}{y!}\\
f_{i'+x,\frac{|j'-x|}{2}}=g_{i',j'}\frac{1}{x!}
\end{aligned}
\right.\)
有了转移式，还要知道 \(x,y\) 的范围
首先 \(x+y>0,\;x+y\ge j\)，且 \(x+y\le n-i\)
综合一下 \(x\le n-i,\;y\le n-i,\;x+j'\ge 0,\;2|y-x+j\) 且 \(x+y>0\)
前面的限制都好满足，但 \(x+y>0\) 不太好满足
我们钦定 \(x\ge 0,\;y>0\)，这样会漏掉 \(x>0,\;y=0\) 的情况，暴力转移即可
边界为 \(f_{1,0}=f_{1,1}=n!\)，答案为 \(f_{n,0}\)
时间复杂度 \(O(n^3)\)
点击查看代码
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int N=55,P=1e9+7;
int n,f[N][N],g[N][N<<1];
int fac[N],ifac[N],C[N][N];
//f[i][j]：有i个点，当前层有j个点儿子个数为奇数的方案数
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
int qmi(int a,int b){
int res=1;
for(;b;b>>=1){ if(b&1) res=1ll*res*a%P;a=1ll*a*a%P;}
return res;
}
int main(){
n=read();
C[0][0]=1;
F(i,1,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;}
fac[0]=1;
F(i,1,n) fac[i]=1ll*fac[i-1]*i%P;
ifac[n]=qmi(fac[n],P-2);
DF(i,n-1,0) ifac[i]=1ll*ifac[i+1]*(i+1)%P;
f[1][0]=f[1][1]=fac[n];
F(i,1,n){
F(j,0,n<<1) if(g[i][j]) F(x,0,n-i) if(x+j-n>=0) if(~(j-n-x)&1) inc(f[i+x][abs((j-n-x)/2)],1ll*g[i][j]*ifac[x]%P);
F(j,0,i){
if(f[i][j]) F(y,1,n-i) inc(g[i+y][y-j+n],1ll*f[i][j]*ifac[y]%P);
//y=0
F(k,max(1,j),n-i) if(~(k-j)&1){
int t=(k-j)/2;
inc(f[i+k][abs(t-k)],1ll*f[i][j]*C[n-i][k]%P*ifac[n-i]%P*fac[n-i-k]%P);
}
}
}
printf("%d\n",f[n][0]);
return 0;
}