CF1799G Count Voting 题解

· · 题解

一

首先，发现这个要求是交错的，不好直接 DP，考虑容斥。我们有两种容斥的方向：

这里我选择的是第二种容斥方法，但我觉得第一种也是可做的。

考虑一组一组地进行 DP，我们设 f_{i,j} 为我们考虑到了第 i 组，前 i 组钦定了 j 个人必须给自己组投票的方案数，len_i 为第 i 组的人数。那么 f 的转移应为：

f_{i,j}=\sum_{k=0}^{\min(j,len_i)}f_{i-1,j-k}\cdot g_{i,k}

上式的意义即为我们枚举第 i 组投给自己的人数，做一个背包。关键变为求出第 i 组钦定 k 个人的方案数 g_{i,k}。下面默认以任一组为例。

考虑如下情况：如果我们知道，第 i 个人的 c_i 张票中，有 a_i 张票是自己组的人投的，有 \sum a_i=k。假如到了 i，还剩 j 个人，那我们选择组内给这个人投的方案数为 \binom{j}{a_i}，总共剩下没有钦定的 len-k 个人，要分给所有 c_i-a_i 里面，这部分是可重集排列，总的贡献为 \frac{(n-\sum k)!}{\prod(c_i-a_i)!}，但我们要 DP，不能直接得到后面的贡献，发现分子不变，考虑把分母拆到每一种方案里。

这样 g 的转移就呼之欲出了（注意因为每一组不干扰，这里 g 的意义改为对于某一组，g_{i,j} 为考虑到第 i 个人，分了 j 张给自己组的票的方案数）：

g_{i,j}=\sum_{k=0}^{\min(j,c_i)} g_{i-1,j-k}\frac{1}{(c_i-k)!}\binom{len-j+k}{k}

最后整理一下，我们对于每一组，先做一遍对 g 的 DP，然后转移 f。

然后经典容斥原理：

ans=\sum_{i=0}^n f_{m,i}(-1)^i (n-i)!

二

总时间复杂度是 n^2 的，不会多项式科技卷积。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define mod 998244353
using namespace std;

int n,m;
int c[205];
int t[205];
int b[205];
int len[200];
int slen[205];
int a[205][205];
ll f[205][205];
ll g[205][205];
ll inv[205];
ll fac[205];
ll infac[205];

inline ll C(int a,int b){return fac[a]*infac[b]%mod*infac[a-b]%mod;}

inline void init(int id){
    g[0][0]=1;
    for(int i=1;i<=len[id];i++){
        for(int j=0;j<=len[id];j++){
            g[i][j]=0;
            for(int k=0;k<=j&&k<=a[id][i];k++)
                (g[i][j]+=g[i-1][j-k]*infac[a[id][i]-k]%mod*C(len[id]-j+k,k))%=mod;
        }
    }
    return ;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&c[i]);
    for(int i=1;i<=n;i++) scanf("%d",&t[i]),b[i]=t[i];
    sort(b+1,b+1+n);
    m=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++){
        t[i]=lower_bound(b+1,b+1+m,t[i])-b;
        len[t[i]]++;
        slen[t[i]]+=c[i];
        a[t[i]][len[t[i]]]=c[i];
    }
    fac[0]=fac[1]=infac[0]=infac[1]=inv[1]=1;
    for(int i=2;i<=n;i++){
        fac[i]=fac[i-1]*i%mod;
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        infac[i]=infac[i-1]*inv[i]%mod;
    }
    f[0][0]=1;
    for(int i=1;i<=m;i++){
        init(i);
        for(int j=0;j<=n;j++){
            for(int k=0;k<=j&&k<=len[i];k++)
                (f[i][j]+=f[i-1][j-k]*g[len[i]][k]%mod)%=mod;
        }
    }
    ll ans=0;
    for(int i=0;i<=n;i++){
        ll x=f[m][i]*fac[n-i]%mod;
        if(i&1) x=mod-x;
        (ans+=x)%=mod;
    }
    printf("%lld\n",ans);

    return 0;
}