九条可怜是一个喜欢树的女孩子,她想生成两棵均有 n 个节点的树。
第一棵树的生成方式是:
- 节点 1 作为树的根。
- 对于 i∈[2,n],从 [1,i−1] 中选取一个节点作为 i 的父亲。
第二棵树的生成方式是:
- 节点 n 作为树的根。
- 对于 i∈[1,n−1],从 [i+1,n] 中选取一个节点作为 i 的父亲。
九条可怜希望对于任意 i∈[1,n],若第一棵树中的节点 i 为叶子,那么第二棵树中的节点 i 为非叶子;若第一棵树中的节点 i 为非叶子,那么第二棵树中的节点 i 为叶子。一个节点被称为叶子当且仅当没有节点的父亲是它。
九条可怜希望你统计生成两棵树的方案数是多少。具体地,你需要对于所有 n∈[2,N] 都计算方案数。两种方案不同当且仅当存在一棵树中的一个节点 i,两种方案中它的父亲不同。因为答案可能很大,你只需要输出答案对 M 取模后的结果。
2≤N≤500,10≤M≤230。
设 f(S) 表示叶子节点集合为 S 时第一棵树的方案数,g(T) 表示叶子节点集合为 T 时第二棵树的方案数,那么有
ans=S∩T=∅,S∪T={1,2,3,…,n}∑f(S)g(T)
发现非叶子节点非常难处理,所以不妨设 f′(S) 表示非叶子节点集合为 S 是第一棵树的方案树,设 g’(T) 表示非叶子节点集合为 T 时第二棵树的方案数,那么有
ans=S∩T=∅,S∪T={1,2,3,…,n}∑f(S)g(T)=S∩T=∅,S∪T={1,2,3,…,n}∑S′∈S,T′∈T∑f′(S′)g′(T′)(−1)n−∣S′∣−∣T′∣=S′∩T′=∅∑f′(S′)g′(T′)(−1)n−∣S′∣−∣T′∣2n−∣S′∣−∣T′∣(S′ 和 T′ 之外的节点可以出现在 S 或 T 中)=S′∩T′=∅∑f′(S′)g′(T′)(−2)n−∣S′∣−∣T′∣
那么设 dpi,j,k 表示处理到 i,∣S′∩{1,2,3,…,i}∣=j,∣T′∩{i+1,i+2,i+3,…,n}∣=k 时的 f′(S′)g′(T′)(−2)n−∣S′∣−∣T′∣,有转移:
- j×k×dpi,j,k→dpi+1,j+1,k
- j×k×dpi,j,k→dpi+1,j,k−1
- −2×j×k×dpi,j,k→dpi+1,j,k
边界条件 dp1,1,k=1,1≤k≤n−1。
答案为 i=1∑n−1dpn−1,i,1×i。
#include <iostream>
#include <cstdio>
using namespace std;
const int S=505;
int n,p;
int dp[S][S][S];
inline void addd(int &x,int y)
{
x+=y;
if(x>=p) x-=p;
}
int main()
{
scanf("%d%d",&n,&p);
for(int i=1;i<=n-1;i++) dp[1][1][i]=1;
for(int i=1;i<=n-1;i++)
{
for(int j=1;j<=i;j++)
{
for(int k=1;k<=n-i;k++)
{
addd(dp[i+1][j+1][k],1ll*j*k%p*dp[i][j][k]%p);
addd(dp[i+1][j][k-1],1ll*j*k%p*dp[i][j][k]%p);
addd(dp[i+1][j][k],p-2ll*j*k%p*dp[i][j][k]%p);
}
}
}
for(int i=2;i<=n;i++)
{
int ans=0;
for(int j=1;j<=n-1;j++) addd(ans,1ll*dp[i-1][j][1]*j%p);
printf("%d\n",ans);
}
return 0;
}