[ABC235G] Gardens
题目描述：
有三种不同颜色的球，分别有 \(A,B,C\) 个。（相同颜色的球之间不区分）
将球放入 \(N\) 个不同的盒子中，要求：
-
每个盒子至少放了一个球
-
每个盒子不能存在两个相同颜色的球
-
可以不放完所有的球
求放置方案数对 \(998244353\) 取模的结果。
对于 \(100\%\) 的数据，保证：$ 1\le N\le 5\times 10^6 $，\(0\le A,B,C\le N\)。
题目分析：
考虑如果没有第一个限制，那么答案就是：
\[\sum_{i=0}^{A}\binom{n}{i}\times \sum_{i=0}^{B}\binom{n}{i} \times \sum_{i=0}^{C}\binom{n}{i}
\]
考虑加上第第一个限制怎么做，我们设 \(g(i)\) 表示 \(i\) 个位置不受限制的方案数，\(f(i)\) 表示 \(i\) 个位置每个位置上至少有一个球的方案数，则：
\[g(n)=\sum_{i=0}^{n}\binom{n}{i}f(i) \\
g(n)=\sum_{i=0}^{A}\binom{n}{i}\times \sum_{i=0}^{B}\binom{n}{i} \times \sum_{i=0}^{C}\binom{n}{i}
\]
可以二项式反演一下得到：
\[f(n)=\sum_{i=0}^{n}(-1)^{n-i}\binom{n}{i}g(i)
\]
那么现在问题变成怎么快速求得 \(g(i)\)，设 \(h(i)=\sum_{i=0}^{A}\binom{n}{i}\)，因为 \(\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}\)，所以：
\[h(i+1)=\sum_{j=0}^{A}\binom{i+1}{j}=\sum_{j=0}^{A}\binom{i}{j}+\sum_{j=0}^{A}\binom{i}{j-1}=\sum_{j=0}^{A}\binom{i}{j}+\sum_{j=1}^{A+1}\binom{i}{j-1}-\binom{i}{A}=2\times h(i)-\binom{i}{A}
\]
可以递推预处理得到，复杂度线性。
代码：
const int INF=1e9+7;
const int N=6e6+7;
const int mod=998244353;
int f[N],g[N],h[N];
int fac[N],ifac[N];
int n,A,B,C;
int qmi(int a,int k){
int res=1;
while(k){
if (k&1) res=res*a%mod;
a=a*a%mod;k>>=1;
}return res;
}
int binom(int n,int m)
{
if (n<m||n<0||m<0) return 0;
return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
signed main(){
scanf("%lld%lld%lld%lld",&n,&A,&B,&C);
fac[0]=1;int inv2=qmi(2,mod-2);
for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
ifac[n]=qmi(fac[n],mod-2);
for (int i=n-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
for (int i=0;i<=A;i++) f[n]=(f[n]+binom(n,i))%mod;
for (int i=n-1;i>=0;i--) f[i]=(f[i+1]+binom(i,A))%mod*inv2%mod;
for (int i=0;i<=B;i++) g[n]=(g[n]+binom(n,i))%mod;
for (int i=n-1;i>=0;i--) g[i]=(g[i+1]+binom(i,B))%mod*inv2%mod;
for (int i=0;i<=C;i++) h[n]=(h[n]+binom(n,i))%mod;
for (int i=n-1;i>=0;i--) h[i]=(h[i+1]+binom(i,C))%mod*inv2%mod;
int ans=0;
for (int i=0;i<=n;i++)
ans=(ans+(((n-i)&1)?mod-1:1)*binom(n,i)%mod*f[i]%mod*g[i]%mod*h[i]%mod)%mod;
printf("%lld\n",ans);
return 0;
}