UOJ #390. 【UNR #3】百鸽笼

看这道题之前先看一道相似的题目 。

考虑类似的容斥：

我们不妨设处理\(1\)的概率。

我们令集合\(T\)中的所有鸽笼都在\(1\)变空之前不为空的，其它的鸽笼随便。要做到这一点，我们只需要令每个\(T\)集合中的鸽笼容量\(--\)就行了。然后我们用背包背出所有序列的方案数(不包括\(1\))，然后在将\(1\)插入序列中。插入时，将\(w_i-1\)个随便插入，然后再将一个放在序列末尾。

具体实现时，我们可以枚举"\(1\)"，然后对其它的鸽笼进行背包。但是复杂度会达到\(O(n^6)\)。于是我们先对所有鸽笼进行背包，计算"\(1\)"的时候直接将它的贡献消除，也就是做"反背包"。复杂度就是\(O(n^5)\)。

代码：

#include
    
     #define ll long long#define N 35#define mod 998244353using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n,w[N];ll ksm(ll t,ll x) {    ll ans=1;    for(;x;x>>=1,t=t*t%mod)        if(x&1) ans=ans*t%mod;    return ans;}ll fac[1005],inv[1005];ll C(int n,int m) {    if(n
     
      =0;i--) inv[i]=inv[i+1]*(i+1)%mod;    n=Get();    for(int i=1;i<=n;i++) w[i]=Get();    g[0][0]=1;    for(int i=1;i<=n;i++) {        sum+=w[i]-1;        for(int j=i;j>=1;j--) {            for(int k=sum;k>=0;k--) {                for(int q=0;q
      
       <=k;q++) {                    (g[j][k]+=g[j-1][k-q]*C(k,q))%=mod;                }            }        }    }    for(int i=1;i<=n;i++) solve(i);    return 0;}