有三种不同颜色的球,分别有 A,B,C 个。(相同颜色的球之间不区分)
将球放入 N 个不同的盒子中,要求:
-
每个盒子至少放了一个球
-
每个盒子不能存在两个相同颜色的球
-
可以不放完所有的球
求放置方案数对 998244353 取模的结果。
1≤N≤5×106,0≤A,B,C≤N
考虑枚举有多少个花圃种了花,然后容斥,有:
ans=i=1∑n(−1)n−i(in)j=0∑A,i(ji)j=0∑B,i(ji)j=0∑C,i(ji)
发现后面那三个求和形式都是 j=0∑m,n(jn),那么不妨设 dpn,m=j=0∑m,n(jn),显然若 n≤m 那么 dpn,m=2n,否则考虑这样一个网格图:
显然 dpn,m 就相当于从 (0,0) 向上向右走到 (n,0),(n−1,1),(n−2,2),…,(n−m,m) 的方案数。那么考虑从 dpn−1,m 递推到 dpn,m,也就是从所有橙色的点向上向右走到蓝色的点的方案数。
观察到除了最后一个点,其它点向上或者向右都能走到蓝色的点,最后一个点却只能向上走走到蓝色的点。那么不妨让所有点都能向上向右走,求出方案数,再减去走到最后一个点再向右走的方案数。显然第一部分的方案数是 2dpn−1,m,而减掉的方案数是 (mn−1)。