[ABC235G] Gardens-526互联

[ABC235G] Gardens

题目描述：

有三种不同颜色的球，分别有 $A,B,C$ 个。（相同颜色的球之间不区分）

将球放入 $N$ 个不同的盒子中，要求：

每个盒子至少放了一个球
每个盒子不能存在两个相同颜色的球
可以不放完所有的球

求放置方案数对 $998244353$ 取模的结果。

数据范围

$ 1\ \leq\ N\ \leq\ 5\ \times\ 10^6 $
$ 0\ \leq\ A\ \leq\ N $
$ 0\ \leq\ B\ \leq\ N $
$ 0\ \leq\ C\ \leq\ N $

思路：

观察题目，确定这是一道计数题，则考虑先列出式子，然后再想办法优化

这里先给出方程 $\sum\limits_{i=0}^{n}(-1)^i\times \sum\limits_{a=0}^{\min(n-i,A)}\binom{n-i}{a}\times \sum\limits_{b=0}^{\min(n-i,B)}\binom{n-i}{b}\times \sum\limits_{c=0}^{\min(n-i,C)}\binom{n-i}{c}$

对于这个方程我稍微解释一下。如果我们不考虑题目中 每个盒子至少放一个球 这个条件，我们可以暂时忽略一下，则方案数为 $\sum\limits_{a=0}^{\min(n,A)}\binom{n}{a}\times \sum\limits_{b=0}^{\min(n,B)}\binom{n}{b}\sum\limits_{c=0}^{\min(n,C)}\binom{n}{c}$

然后我们就需要去考虑到怎么处理这个限制条件了。考虑容斥，列出一个非常经典的方程，就是最开始的式子。

然后我们发现现在问题便来到如何求出 $\sum\limits_{a=0}^{\min(n-i,A)}\binom{n-i}{a}$，不妨令 $f_i=\sum\limits_{a=0}^{\min(i,A)}\binom{i}{a}$

然后我们直接暴力推式子：

\[f_{i+1}=\sum\limits_{j=0}^{A}\binom{i+1}{j}=\sum\limits_{j=0}^{A}\binom{i}{j}+\sum\limits_{j=0}^{A}\binom{i}{j-1}=\sum\limits_{j=0}^{A}\binom{i}{j}+\sum\limits_{j=1}^{A+1}\binom{i}{j-1}-\binom{i}{A}=2\times f_i-\binom{i}{A} \]

通过这个式子，我们就得到了 $f_{i+1}=2\times f_i-\binom{i}{A}$ 这个式子。然后又可以推得：$f_{i}=\frac{f_{i+1}+\binom{i}{A}}{2}$

然后就可以快乐得算答案了

点击查看代码

#include<bits/stdc++.h>
#define int long long
#define mem(a) memset(a,0,sizeof(a))
#define set(a,b) memset(a,b,sizeof(a))
#define ls i<<1
#define rs i<<1|1
#define pb(x) push_back(x)
#define pt(x) putchar(x)
#define T int t;cin>>t;while(t--)
#define rand RAND
using namespace std;
char buf[1<<20],*p1,*p2;
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
template<class Typ> Typ &re(Typ &x){char ch=gc(),sgn=0; x=0;for(;ch<'0'||ch>'9';ch=gc()) sgn|=ch=='-';for(;ch>='0'&&ch<='9';ch=gc()) x=x*10+(ch^48);return sgn&&(x=-x),x;}
template<class Typ> void wt(Typ x){if(x<0) putchar('-'),x=-x;if(x>9) wt(x/10);putchar(x%10^48);}
const int maxn=5e6+5;
const int mod=998244353;
int seed = 19243;
unsigned rand(){return seed=(seed*48271ll)%2147483647;}
int fac[maxn],inv[maxn];
int qp(int x,int k){
    int res=1;
    while(k){
        if(k&1)res=res*x%mod;
        x=x*x%mod;k>>=1;
    }
    return res;
}
void init(){
    int N=maxn-5;
    fac[0]=1;
    for(int i=1;i<=N+1;i++)fac[i]=fac[i-1]*i%mod;
    inv[N+1]=qp(fac[N+1],mod-2);
    for(int i=N;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
}
int n,a,b,c;
int f[maxn],g[maxn],h[maxn];
int C(int n,int m){
    if(n<m||n<0||m<0)return 0;
    return fac[n]*inv[n-m]%mod*inv[m]%mod;
}
signed main(){
    init();
    cin>>n>>a>>b>>c;
    for(int i=0;i<=a;i++)f[n]=(f[n]+C(n,i))%mod;
    for(int i=n-1;i>=0;i--){
        f[i]=(f[i+1]+C(i,a))%mod;
        f[i]=(f[i]*(mod+1)/2)%mod;
    }
    for(int i=0;i<=b;i++)g[n]=(g[n]+C(n,i))%mod;
    for(int i=n-1;i>=0;i--){
        g[i]=(g[i+1]+C(i,b))%mod;
        g[i]=(g[i]*(mod+1)/2)%mod;
    }
    for(int i=0;i<=c;i++)h[n]=(h[n]+C(n,i))%mod;
    for(int i=n-1;i>=0;i--){
        h[i]=(h[i+1]+C(i,c))%mod;
        h[i]=(h[i]*(mod+1)/2)%mod;
    }
    int ans=0;
    for(int i=0;i<=n;i++){
        int tmp=(i&1?mod-1:1);
        tmp=tmp*C(n,i)%mod*f[n-i]%mod*g[n-i]%mod*h[n-i]%mod;
        ans=(ans+tmp)%mod;
    }
    cout<<ans<<endl;
    return 0;
}

abstractions programming笔记235