题目描述
九条可怜是一个喜欢树的女孩子，她想生成两棵均有 \(n\) 个节点的树。
第一棵树的生成方式是：
- 节点 \(1\) 作为树的根。
- 对于 \(i \in [2, n]\)，从 \([1, i - 1]\) 中选取一个节点作为 \(i\) 的父亲。
第二棵树的生成方式是：
- 节点 \(n\) 作为树的根。
- 对于 \(i \in [1, n - 1]\)，从 \([i + 1, n]\) 中选取一个节点作为 \(i\) 的父亲。
九条可怜希望对于任意 \(i \in [1, n]\)，若第一棵树中的节点 \(i\) 为叶子，那么第二棵树中的节点 \(i\) 为非叶子；若第一棵树中的节点 \(i\) 为非叶子，那么第二棵树中的节点 \(i\) 为叶子。一个节点被称为叶子当且仅当没有节点的父亲是它。
九条可怜希望你统计生成两棵树的方案数是多少。具体地，你需要对于所有 \(n \in [2, N]\) 都计算方案数。两种方案不同当且仅当存在一棵树中的一个节点 \(i\)，两种方案中它的父亲不同。因为答案可能很大，你只需要输出答案对 \(M\) 取模后的结果。
提示
对于所有测试点：保证 \(2 \le N \le 500\)，\(10 \le M \le 2^{30}\)。
每个测试点的具体限制见下表：
| 测试点编号 | \(N \le\) | 特殊限制 |
|---|---|---|
| \(1\) | \(10\) | 无 |
| \(2\) | \(20\) | 保证 \(M\) 为质数 |
| \(3\) | \(50\) | 无 |
| \(4\) | \(50\) | 保证 \(M\) 为质数 |
| \(5\) | \(100\) | 无 |
| \(6\) | \(100\) | 保证 \(M\) 为质数 |
| \(7\) | \(500\) | 无 |
| \(8\) | \(500\) | 保证 \(M\) 为质数 |
| \(9\) | \(500\) | 无 |
| \(10\) | \(500\) | 保证 \(M\) 为质数 |
题解：
\[\begin{align*} f(T_1)表示第一棵树非叶子集合恰好为T_1时，构造出第一棵树的方案数。\\ g(T_2)表示第二棵树非叶子集合恰好为T_2时，构造出第二棵树的方案数。\\ \end{align*} \]所求即为：
\[\begin{align*} f'(T_1)表示第一棵树非叶子集合包含于T_1时，构造出第一棵树的方案数\\ g'(T_2)表示第二棵树非叶子集合包含于T_2时，构造出第二棵树的方案数\\ \sum\limits_{T1\bigcap T_2=\varnothing,T1\bigcup T_2=\{1,2,3,...,n\}}f(T_1)g(T_2)=\sum\limits_{T1\bigcap T_2=\varnothing,T1\bigcup T_2=\{1,2,3,...,n\}}\sum\limits_{S\subseteq T_1,T\subseteq T_2}f'(S)g'(T)(-1)^{|T_1|+|T_2|-|S|-|T|}\\ \end{align*} \]变换一下：
\[\begin{align*} &\sum\limits_{T1\bigcap T_2=\varnothing,T1\bigcup T_2=\{1,2,3,...,n\}}\sum\limits_{S\subseteq T_1,T\subseteq T_2}f'(S)g'(T)(-1)^{|T_1|+|T_2|-|S|-|T|}\\ =& \sum\limits_{S\bigcap T=\varnothing}f'(S)g'(T)(-1)^{n-|S|-|T|}2^{n-|S|-|T|}\\ =& \sum\limits_{S\bigcap T=\varnothing}f'(S)g'(T)(-2)^{n-|S|-|T|} \end{align*} \]考虑给定\(S\)，如何计算\(f'(S)\)
对于节点\(i\in[2,n]\)，\(fa_i\)可能为\([1,i-1]\)中的任意一个非叶子节点，那么方案数即为\([1,i-1]\)中的非叶子节点个数
\(g'\)的计算同理
DP，设\(f_{i,j,k}\)表示决策到第\(i\)个点，\(|\{1,...,i\}\bigcap S|=j,|\{i+1,...,n\}\bigcap T|=k\)方案数
初值为\(f_{1,1,i}=1,(1<=i<=n-1)\)
转移枚举\(i\)属于\(S\)，还是属于\(T\)，还是既不属于\(S\)也不属于\(T\)即可
\[\begin{align*} &1.i属于S,f_{i,j+1,k}+=(f_{i-1,j,k}*j*k)\\ &2.i属于T,f_{i,j,k-1}+=(f_{i-1,j,k}*j*k)\\ &3.i既不属于S也不属于T,f_{i,j,k}+=(-2*f_{i-1,j,k}*j*k)\\ \end{align*} \]代码：
#include<bits/stdc++.h>
#define For(i,l,r) for(int i=(l);i<=(r);++i)
const int N=510;
typedef long long ll;
using namespace std;
int n;
ll M;
ll f[2][N][N];
int main()
{
scanf("%d%lld",&n,&M);
For(i,1,n-1)
f[1][1][i]=1;
int pr_e=0,no_w=1;
For(i,2,n)
{
pr_e^=1;
no_w^=1;
memset(f[no_w],0,sizeof(f[no_w]));
ll ans=0;
For(j,1,i-1)
{
ll tmp=((1ll*f[pr_e][j][1]*j)%M);
(ans+=tmp)%=M;
}
printf("%lld\n",ans);
For(j,1,i-1)
{
For(k,1,n-i+1)
{
ll tmp1=((1ll*f[pr_e][j][k]*j*k)%M);
ll tmp2=((1ll*f[pr_e][j][k]*j*k)%M);
ll tmp3=((1ll*2*f[pr_e][j][k]*j*k)%M);
tmp3*=(-1);
(tmp3+=M)%=M;
(f[no_w][j+1][k]+=tmp1)%=M;
(f[no_w][j][k-1]+=tmp2)%=M;
(f[no_w][j][k]+=tmp3)%=M;
}
}
}
return 0;
}