CTS2019 氪金手游

题目链接

考虑我们现在只会外向树的dp，现在想办法如何处理反向的边。

考虑容斥，计算至少有\(i\)条边不合法的情况，容斥系数是\((-1)^i\)

这个容斥可以用dp来做，这题就完了。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
inline int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
inline int sub(int a,int b){a-=b;return a<0?a+mod:a;}
inline int mul(int a,int b){return (ll)a*b%mod;}
inline int qpow(int a,int b){int ret=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ret=mul(ret,a);return ret;}
inline int qinv(int x){return qpow(x,mod-2);}
/* math */
const int N = 1010;
int hed[N],to[N<<1],nxt[N<<1],cnt=1;
inline void adde(int u,int v){
    ++cnt;to[cnt]=v,nxt[cnt]=hed[u];hed[u]=cnt;
}
int n;
int f[N][N*3];
int p[N][4];
int sz[N];

inline void dfs(int x,int pre){
    f[x][0]=1;
    sz[x]=0;
    for(int i=hed[x];i;i=nxt[i]){
        int v=to[i];if(v==pre)continue;
        int dir=(i&1)^1;//dir==1::u to v
        dfs(v,x);
        vector<int> g(sz[x]+sz[v]+1,0);
        if(dir){
            for(int i=sz[x];~i;i--){
                for(int j=0;j<=sz[v];j++){
                    g[i+j]=add(g[i+j],mul(f[x][i],f[v][j]));
                }
            }
        }else{
            int V=0;
            for(int i=0;i<=sz[v];i++)V=add(V,f[v][i]);
            for(int i=0;i<=sz[x];i++)g[i]=mul(f[x][i],V);
            for(int i=sz[x];~i;i--){
                for(int j=0;j<=sz[v];j++){
                    g[i+j]=sub(g[i+j],mul(f[x][i],f[v][j]));
                }
            }
        }
        sz[x]+=sz[v];
        for(int i=0;i<=sz[x];i++)f[x][i]=g[i];
    }
    sz[x]+=3;
    for(int i=sz[x];~i;i--){
        f[x][i]=0;int Inv=qinv(i);
        if(i>=1)f[x][i]=add(f[x][i],mul(mul(f[x][i-1],p[x][1]), mul(1,Inv)));
        if(i>=2)f[x][i]=add(f[x][i],mul(mul(f[x][i-2],p[x][2]), mul(2,Inv)));
        if(i>=3)f[x][i]=add(f[x][i],mul(mul(f[x][i-3],p[x][3]), mul(3,Inv)));
    }
    // for(int i=0;i<=sz[x];i++)cout << f[x][i] << endl;
}


int main()
{
    cin >> n;
    for(int i=1;i<=n;i++){
        int a[3],tot=0;
        for(int j=0;j<3;j++)scanf("%d",&a[j]),tot=add(tot,a[j]);
        tot=qpow(tot,mod-2);
        for(int j=1;j<=3;j++)p[i][j]=mul(a[j-1],tot);
    }
    for(int i=1;i<n;i++){
        int u,v;scanf("%d%d",&u,&v);
        adde(u,v);adde(v,u);
    }
    dfs(1,0);
    int ans=0;
    for(int i=0;i<=sz[1];i++)ans=add(ans,f[1][i]);
    cout << ans << endl;
}

CTS2019 氪金手游

原文：https://www.cnblogs.com/weiyanpeng/p/11048439.html