MornStar @ 2024-07-22 16:48:26
rt，求：
\sum_{B_1+B_2+\cdots+B_n=M}\prod_{i=1}^n{B_i^{\underline{A_i}}}
by 飞雨烟雁 @ 2024-07-22 18:06:00
@MornStar 若记 f_n(x) 为：
f_n(x)=\sum_{k=0}^\infty k^{\underline n}x^k
则答案可用生成函数写为：
[x^M]\prod_{i=1}^n f_{A_i}(x)
对于 f_n{(x)}，容易发现它等于 x^n[ 1/(1-x)]^{(n)}=n!x^n/(1-x)^{n+1}。
记 a=\sum A_i，上式可化简为：
[x^M]\prod_{i=1}^n \dfrac{A_i!x^{A_i}}{(1-x)^{A_i+1}}=[x^M]\dfrac{x^{a}}{(1-x)^{a+n}}\prod_{i=1}^n A_i!=\binom{M+n-1}{a+n-1}\prod_{i=1}^n A_i!
直接计算即可，时间复杂度 \mathcal O(a)=\mathcal O(An)。