题解

思路

设第 $i$ 种元素取 $c_i$ 个。组合数是满足 $0\le c_i\le k_i$ 且 $\sum c_i=r$ 的向量数；固定向量对应的排列数为 $r!/\prod c_i!$。

因此组合数是

$$[x^r]\prod_i(1+x+\cdots+x^{k_i}),$$

排列数是

$$r![x^r]\prod_i\left(1+x+\frac{x^2}{2!}+\cdots+\frac{x^{k_i}}{k_i!}\right).$$

若 $r>\sum k_i$ 可直接输出 0 0，所以真正参与计算的次数不超过 $10000$。

做法

tiny：枚举取用数量

深度优先枚举每个 $c_i$，到末尾检查总和，并用逆阶乘累加排列贡献。

medium：背包卷积

依次加入每一种元素。组合 DP 转移权为 $1$；排列的指数生成函数 DP 转移权为 $1/j!$。最后给排列系数乘 $r!$。

特殊性质 $k_i=1$

此时所有元素互异。若 $r\le n$，组合数为 $\binom nr$，排列数为 $n!/(n-r)!$；否则均为 $0$。

满分：NTT 分治乘积

组合数仍可用滑动窗口背包在 $O(nr)$ 内求出。排列数把每个多项式

$$P_i(x)=\sum_{j=0}^{\min(k_i,r)}\frac{x^j}{j!}$$

放入分治乘积树，用 NTT 合并，并在每次合并后截断到 $r$ 次。最终取 $x^r$ 系数乘 $r!$。

正确性证明

组合生成函数中，从第 $i$ 个因子选择 $x^{c_i}$ 恰好表示取 $c_i$ 个第 $i$ 种元素，系数均为 $1$，故 $x^r$ 系数恰为全部合法计数向量数。

指数生成函数中，同一选择的系数为 $1/\prod c_i!$。乘以 $r!$ 后得到该多重集合排列的多项式系数 $r!/\prod c_i!$。对所有合法向量求和即为排列总数。NTT 只改变多项式乘法的计算方式，截断高于 $r$ 的项不可能影响 $x^r$ 系数，所以答案正确。

复杂度

• tiny：取决于枚举状态数；
• medium：$O(nr\max k_i)$ 时间，$O(r)$ 空间；
• 特殊性质：$O(n)$ 时间；
• 满分：组合 DP 为 $O(nr)$，排列乘积为 $O(K\log K\log n)$，其中 $K=\min(r,\sum k_i)\le10000$；空间 $O(K\log n)$。