这里给出一种容斥+多项式的做法
复杂度为是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; }