好的容斥题目。
容易发现DP过程中直接钦定叶子是不好做的，并且需要满足并集为全集。很容易想到使用容斥去掉这一条件。我们对于非叶子进行考虑：设 $f(S)$ 表示第一棵树中集合 $S$ 为非叶子节点时的方案数， $g(T)$ 表示第二棵树中集合 $T$ 为非叶子节点时的方案数，得到答案为：
直接容斥，设 $f’(S)$ 表示第一棵树中集合 $S’\subseteq S$ 为非叶子节点时的方案数， $g(T)$ 表示第二棵树中集合 $T’\subseteq T$ 为非叶子节点时的方案数，进一步得到：
我们成功将“并集为全集”这一条件去掉。并且这是容易DP的。影响决策的只有 $|S’|,|T’|$，将其压入状态，设 $f(x,i,j)$ 表示考虑到 $x$，$S’$ 有 $i$ 个元素，$T’$ 有 $j$ 个的元素带容斥系数的方案数。我们顺序枚举所有元素，将两棵树以不同的顺序 DP，设边界为 $f(1,1,i)=1$，最终答案为 $\sum_i f(n,i,1)\times i$。考虑转移。对于当前枚举的元素 $x$，可以选择 $S’$ 中任意元素作为第一棵树上的父亲，和选择 $T’$ 中任意元素作为第二棵树上的父亲。所以转移系数为 $i\times j$。现在考虑是否将 $x+1$ 放进 $S’,T’$ 里，分类讨论一下：
$(1).x\in S’$，钦定 $x+1$ 为第二棵树的叶子， $i\times j\times f(x,i,j)\to f(x+1,i+1,j)$。
$(2).x\in T’$，钦定 $x+1$ 为第一棵树的叶子， $i\times j\times f(x,i,j)\to f(x+1,i,j-1)$。
$(3).x\notin S’,x\notin T’$，钦定 $x+1$ 为第一棵树的叶子和第二棵树的叶子，$-2\times i\times j\times f(x,i,j)\to f(x+1,i,j)$。
需要滚动数组优化空间。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=500+10;
template <class T>
inline void read(T &x)
{
x=0;bool f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,mod;
int p,f[2][N][N];
inline void upd(int &x,int y){x+=y;x=(x>=mod)?x-mod:x;}
int main()
{
read(n,mod);
for(int i=1;i<n;i++)f[p][1][i]=1;
for(int x=1;x<n;x++,p^=1)
{
memset(f[p^1],0,sizeof(f[p^1]));
int ans=0;
for(int i=1;i<=x;upd(ans,1ll*i*f[p][i][1]%mod),i++)
for(int j=1;j<=n-x;j++)
{
upd(f[p^1][i+1][j],1ll*i*j*f[p][i][j]%mod);
upd(f[p^1][i][j-1],1ll*i*j*f[p][i][j]%mod);
upd(f[p^1][i][j],1ll*i*j*(mod-2)%mod*f[p][i][j]%mod);
}
printf("%d\n",ans);
}
return 0;
}
|