全曲最难段
vegetable_king · · 休闲·娱乐
-
请你快速求出所有长度为
k ,总和\le s 的非负整数序列a 的乘积之和。 -
考虑组合意义,相当于
s 个球排成一行,任意插共k + 1 块板,且有一块板插在最前面,每两块板之间都选择一个球的方案数。 -
在非第一块板的每一块后面都放一个球,就相当于在
s + k 个球中选择2k 个球。 -
答案为
\binom{s + k}{2k} 。 -
再给个
l \le k ,求长度为l 的前缀的乘积和。 -
和前面的分析是一样的,改成
\binom{s + k}{l + k} 即可。