ABC235G Gardens 做题记录

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

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

• 每个盒子至少放了一个球

• 每个盒子不能存在两个相同颜色的球

• 可以不放完所有的球

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

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

考虑枚举有多少个花圃种了花，然后容斥，有：

$ans=\sum\limits_{i=1}^{n}(-1)^{n-i}\dbinom{n}{i}\sum\limits_{j=0}^{A,i}\dbinom{i}{j}\sum\limits_{j=0}^{B,i}\dbinom{i}{j}\sum\limits_{j=0}^{C,i}\dbinom{i}{j}$

发现后面那三个求和形式都是 $\sum\limits_{j=0}^{m,n}\dbinom{n}{j}$，那么不妨设 $dp_{n,m}=\sum\limits_{j=0}^{m,n}\dbinom{n}{j}$，显然若 $n\le m$ 那么 $dp_{n,m}=2^n$，否则考虑这样一个网格图：

显然 $dp_{n,m}$ 就相当于从 $(0,0)$ 向上向右走到 $(n,0),(n-1,1),(n-2,2),\dots,(n-m,m)$ 的方案数。那么考虑从 $dp_{n-1,m}$ 递推到 $dp_{n,m}$，也就是从所有橙色的点向上向右走到蓝色的点的方案数。

观察到除了最后一个点，其它点向上或者向右都能走到蓝色的点，最后一个点却只能向上走走到蓝色的点。那么不妨让所有点都能向上向右走，求出方案数，再减去走到最后一个点再向右走的方案数。显然第一部分的方案数是 $2dp_{n-1,m}$，而减掉的方案数是 $\dbinom{n-1}{m}$。