牛客练习赛64 - 宝石装箱

这里给出一种容斥+多项式的做法

复杂度为是n^2/2

大家一般是容斥+背包啊，我觉得这里多项式也蛮好写的。

容斥应该不用多说了，设为第i个球合法的情况。套一套下面两个公式。

我们要求的是第二个公式的左半，用第一个公式带入第二个公式的右边第二项。

所得公式的右半边从左向右数第i项(不考虑符号)，表示n个球里面，任选i个不球，这i个球不合法，其他球任意（可合法也可不合法）的方案数。

其他球任意的方案数是种，那么剩下的i个球不合法的方案数是多少嘞。
用下生成函数的方法来表示，第i个箱子有cnt[i]个候选的不合法球，可以选一个不合法球，生成函数表示就是(1+cnt[i]*x)，全部n个箱子对应的生成多项式乘起来，x^k就是选k个不合法球的方案数。

那么就做完了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 998244353;

int a[100010],sum[100010],fac[100010];
void dfs(int x[],int l,int r){
    if(l==r){
        x[0]=1,x[1]=a[l];
        return;
    }
    int mid=l+r>>1;
    int y[mid-l+2]={},z[r-mid+1]={};
    dfs(y,l,mid),dfs(z,mid+1,r);
    for(int i=0;i<=mid-l+1;i++){
        for(int j=0;j<=r-mid;j++){
            x[i+j]=(x[i+j]+1ll*y[i]*z[j])%mod;
        }
    }
}
signed main(){
    int n;cin>>n;fac[0]=1;
    for(int i=1;i<=n;i++){
        int tmp;cin>>tmp;a[tmp]++;
        fac[i]=1ll*fac[i-1]*i%mod;
    }
    dfs(sum,1,n);
    ll ans=0;
    for(int i=0;i<=n;i++){
        ll tmp=1ll*(i&1?-1:1)*fac[n-i]*sum[i]%mod;
        ans=(ans+tmp)%mod;
        // cout<<i<<" "<<tmp<<" "<<sum[i]<<endl;
    }
    cout<<(ans%mod+mod)%mod<<endl;
}