P8329 [ZJOI2022] 树

好的容斥题目。

容易发现DP过程中直接钦定叶子是不好做的，并且需要满足并集为全集。很容易想到使用容斥去掉这一条件。我们对于非叶子进行考虑：设 $f(S)$ 表示第一棵树中集合 $S$ 为非叶子节点时的方案数， $g(T)$ 表示第二棵树中集合 $T$ 为非叶子节点时的方案数，得到答案为：

$$Ans=\sum _{S\cap T=\mathrm{\varnothing },S\cup T=\{1,2,\cdots ,n\}}f(S)g(T)$$

直接容斥，设 $f^{\prime }(S)$ 表示第一棵树中集合 $S^{\prime }\subseteq S$ 为非叶子节点时的方案数， $g(T)$ 表示第二棵树中集合 $T^{\prime }\subseteq T$ 为非叶子节点时的方案数，进一步得到：

$$\begin{array}{rl}Ans=& \sum _{S\cap T=\mathrm{\varnothing },S\cup T=\{1,2,\cdots ,n\}}\sum _{S^{\prime }\subseteq S,T^{\prime }\subseteq T}(-1{)}^{|S|-|S^{\prime }|+|T|-|T^{\prime }|}{f}^{\prime }(S^{\prime })g^{\prime }(T^{\prime })\\ =& \sum _{S^{\prime }\cap T^{\prime }=\mathrm{\varnothing }}(-2{)}^{n-|S^{\prime }|-|T^{\prime }|}{f}^{\prime }(S^{\prime })g^{\prime }(T^{\prime })\end{array}$$

我们成功将“并集为全集”这一条件去掉。并且这是容易DP的。影响决策的只有 $|S^{\prime }|,|T^{\prime }|$，将其压入状态，设 $f(x,i,j)$ 表示考虑到 $x$，$S^{\prime }$ 有 $i$ 个元素，$T^{\prime }$ 有 $j$ 个的元素带容斥系数的方案数。我们顺序枚举所有元素，将两棵树以不同的顺序 DP，设边界为 $f(1,1,i)=1$，最终答案为 $\sum _{i}f(n,i,1)\times i$。考虑转移。对于当前枚举的元素 $x$，可以选择 $S^{\prime }$ 中任意元素作为第一棵树上的父亲，和选择 $T^{\prime }$ 中任意元素作为第二棵树上的父亲。所以转移系数为 $i\times j$。现在考虑是否将 $x+1$ 放进 $S^{\prime },T^{\prime }$ 里，分类讨论一下：

$(1).x\in S^{\prime }$，钦定 $x+1$ 为第二棵树的叶子， $i\times j\times f(x,i,j)\to f(x+1,i+1,j)$。

$(2).x\in T^{\prime }$，钦定 $x+1$ 为第一棵树的叶子， $i\times j\times f(x,i,j)\to f(x+1,i,j-1)$。

$(3).x\notin S^{\prime },x\notin T^{\prime }$，钦定 $x+1$ 为第一棵树的叶子和第二棵树的叶子，$-2\times i\times j\times f(x,i,j)\to f(x+1,i,j)$。

需要滚动数组优化空间。

Code

#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;
}