全曲最难段

vegetable_king · 2025-01-06 15:41:50 · 休闲·娱乐

• 请你快速求出所有长度为 k，总和 \le s 的非负整数序列 a 的乘积之和。

• 考虑组合意义，相当于 s 个球排成一行，任意插共 k + 1 块板，且有一块板插在最前面，每两块板之间都选择一个球的方案数。

• 在非第一块板的每一块后面都放一个球，就相当于在 s + k 个球中选择 2k 个球。

• 答案为 \binom{s + k}{2k}。

• 再给个 l \le k，求长度为 l 的前缀的乘积和。

• 和前面的分析是一样的，改成 \binom{s + k}{l + k} 即可。