[ABC235G] Gardens
taozhiming
·
·
题解
[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}
可以递推预处理得到，复杂度线性。
代码：
code