题解：P12002 吃猫粮的玉桂狗

· · 题解

好题。

题目的意思就是一些东西有个数限制，要把东西丢到树上，然后有几个东西不能按照某种顺序摆。

考虑容斥。

我们先放弃这个个数限制，先算出这种情况下的答案数。

显然，每个点只要记录下这个点是某个颜色的方案数，转移只要把符合条件的儿子乘起来就好了。这一部分是 O(n^4) 的。

代码如下。

void dfs1(int x,int fa){
    if(g[x].size()==1&&fa){
        for(int i=1;i<=m;i++)dp[x][i][0]=1;
    } 
    for(int i:g[x]){
        if(i==fa)continue;
        dfs1(i,x);
        for(int j=1;j<=m;j++){
            ll tmp=0;
            for(int k=1;k<=m;k++){
                if(!s[j][k]){
                    if(dp[x][j][0]==0&&dp[i][k][0]!=0)dp[x][j][0]=1;
                    tmp+=dp[i][k][0];
                    tmp%=mod;
                }
            }
            dp[x][j][0]*=tmp;
            dp[x][j][0]%=mod;
        }
    }
}

然后考虑某个东西个数不够的情况，显然这个东西我们不能直接容斥，不然就爆了，但是题目有个条件还没用到，就是 c_i\ge\frac{n}{2}，这个东西有啥用呢？就是没有两个东西同时用超过的情况，否则放的东西就比 n 还多了。

所以我们可以枚举下每个超出的物品 i，然后每个点记录下这个点的颜色，和 i 的个数。

朴素的 dp 是 O(n^6) 的，代码长这样。

void dfs2(int x,int fa){
    for(int i=1;i<=m;i++)dp[x][i][0]=1;
    for(int i:g[x]){
        if(i==fa)continue;
        dfs2(i,x);
        ll f[N][N]={0};
        for(int j=1;j<=m;j++){
            for(int k=0;k<=n;k++){//当前节点的颜色和标记数量 
                int tmp=0;
                for(int l2=0;l2<=k;l2++){
                    for(int l=1;l<=m;l++){
                        if(s[j][l])continue;
                        f[j][k]+=dp[x][j][k-l2]*dp[i][l][l2];
                    }
                }
            }
        }
        for(int j=1;j<=m;j++)for(int k=0;k<=n;k++)dp[x][j][k]=f[j][k];
    }
    for(int j=n;j>=1;j--)dp[x][mark][j]=dp[x][mark][j-1];
    dp[x][mark][0]=0;
}

考虑如何优化这玩意，其实就是因为枚举每个点使用被标记的东西的个数，导致了统计多次儿子对某个东西的贡献，所以这玩意先与处理下直接用即可，复杂度 O(n^5)。

代码如下。

void dfs2(int x,int fa){
    for(int i=1;i<=m;i++)dp[x][i][0]=1;
    for(int i:g[x]){
        if(i==fa)continue;
        dfs2(i,x);
        ll f[N][N]={0};
        for(int j=1;j<=m;j++){
            for(int k=0;k<=n;k++){//当前节点的颜色和标记数量 
                int tmp=0;
                for(int l2=0;l2<=k;l2++){
                    f[j][k]+=dp[x][j][k-l2]*summ[i][j][l2]%mod;
                    f[j][k]%=mod;
                }
            }
        }
        for(int j=1;j<=m;j++)for(int k=0;k<=n;k++)dp[x][j][k]=f[j][k];
    }
    for(int j=n;j>=1;j--)dp[x][mark][j]=dp[x][mark][j-1];
    dp[x][mark][0]=0;
    for(int j=1;j<=m;j++){
        for(int k=0;k<=n;k++){
            for(int l=1;l<=m;l++){
                if(s[j][l])continue;
                summ[x][j][k]+=dp[x][l][k];
            }
        }
    }
}