ABC235G Gardens 做题记录

有三种不同颜色的球,分别有 A,B,CA,B,C 个。(相同颜色的球之间不区分)

将球放入 NN 个不同的盒子中,要求:

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

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

  • 可以不放完所有的球

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

1N5×1061 \leq N \leq 5 \times 10^60A,B,CN0 \leq A,B,C \leq N

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

ans=i=1n(1)ni(ni)j=0A,i(ij)j=0B,i(ij)j=0C,i(ij)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}

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

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

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