专栏文章

题解：P12002 吃猫粮的玉桂狗

jj23wuyifan
P12002题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minuww76
此快照首次捕获于
2025/12/02 08:45
3 个月前
此快照最后确认于
2025/12/02 08:45
3 个月前
查看原文
一道很好的 dp 题，感觉之前有见过这种套路，一下还是不会做。
题目中的限制 (x,y)(x,y) 相当于是树中不存在父亲是 xx 并且儿子是 yy。观察到题目中有一个特别的条件是：保证 ci≥⌊n2⌋c_i \geq \lfloor\frac{n}{2}\rfloor。这有什么用处呢？这样就可以保证只有最多一种猫粮超出了 cic_i 的限制。考虑容斥，合法的方案即是总的方案数减掉有一种猫粮超出数量限制的方案。总的方案是比较好计算的，f2[u][i]f2[u][i] 表示 uu 节点放的是 ii 这种猫粮其子树内的方案数。有转移：
f2[u][i]=∏v∈son[u](∑i=1mf2[v][j]×[ok(i,j)])f2[u][i] = \prod_{v \in son[u]}(\sum_{i=1}^{m}f2[v][j] \times [ok(i,j)])
其中 ok(i,j)ok(i,j) 表示没有 (i,j)(i,j) 这个限制。总方案数就是：∑i=1mf2[1][i]\sum_{i=1}^{m}f2[1][i]
接下来考虑求有一种猫粮超出数量限制的方案。可以枚举超出限制的猫粮 xx，f[u][i][j]f[u][i][j] 表示在 uu 点的猫粮种类是 ii 一共选了 jj 个种类 xx 的猫粮方案数。有转移：
f′[u][i][j+l]=∑v∈son[u]f[u][i][j]×f[v][k][l]×[ok(i,k)]f'[u][i][j+l]=\sum_{v \in son[u]}f[u][i][j] \times f[v][k][l] \times [ok(i,k)]
总的不合法的方案就是：∑i=c[i]+1n∑j=1mf[1][j][i]\sum_{i=c[i]+1}^{n} \sum_{j=1}^{m} f[1][j][i]
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 55;
const int mod = 353442899;
int n,m,t,c[N];
vector<int> E[N];
bool vis[N][N];
int f[N][N][N],g[N][N],x,ans,sz[N];
//f[u][i][j] 表示在u点的猫粮种类是i一共选了j个种类x的猫粮
inline void dfs(int u,int fa){
    sz[u] = 1;
    for(int i = 1;i <= m;i ++)f[u][i][i == x] = 1;
    for(int v : E[u]){
        if(v == fa)continue;
        dfs(v,u);
        memset(g,0,sizeof(g));
        for(int o = 1;o <= m;o ++){
            for(int i = 1;i <= m;i ++){
                if(vis[o][i])continue;
                for(int j = 0;j <= sz[u];j ++){
                    for(int k = 0;k <= sz[v];k ++)
                        g[o][j + k] += f[u][o][j] * f[v][i][k] % mod;
                }
            }
        }
        sz[u] += sz[v];
        for(int i = 1;i <= m;i ++)
            for(int j = 0;j <= sz[u];j ++)f[u][i][j] = g[i][j] % mod;
    }
}
//g[u][i]表示在u点猫粮种类是i的方案数
int f2[N][N];
inline void dfs2(int u,int fa){
    for(int i = 1;i <= m;i ++)f2[u][i] = 1;
    for(int v : E[u]){
        if(v == fa)continue;
        dfs2(v,u);
        for(int i = 1;i <= m;i ++){
            int cnt = 0;
            for(int j = 1;j <= m;j ++)if(!vis[i][j])
                cnt += f2[v][j];
            f2[u][i] = f2[u][i] * cnt % mod;
        }
    }
}
signed main(){
    cin >> n >> m >> t;
    for(int i = 1;i <= m;i ++)cin >> c[i];
    for(int i = 1;i < n;i ++){
        int u,v;
        cin >> u >> v;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    for(int i = 1;i <= t;i ++){
        int x,y;
        cin >> x >> y;
        vis[x][y] = 1;
    }
    //枚举超出数量限制的猫粮种类
    for(x = 1;x <= m;x ++){
        memset(f,0,sizeof(f));
        dfs(1,0);
        for(int k = 1;k <= m;k ++)
            for(int j = c[x] + 1;j <= n;j ++)ans -= f[1][k][j];
        ans %= mod;
    }
    dfs2(1,0);
    for(int i = 1;i <= m;i ++)ans += f2[1][i];
    ans %= mod;ans = (ans + mod) % mod;
    cout << ans;
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...