3418 [统一省选 2020] 组合数问题 题解

说明

本题解整理自完整数学推导过程，参考这篇博客，重点在于如何从定义严格推出可计算的递推式

注意！ 本题解包含较多组合恒等式与求和变形，请耐心阅读。

简要题意

给定整数 ，以及一个 次多项式

要求计算：

先说结论

定义：

核心递推式

边界条件

最终答案

式子的正确性来自线性叠加性，下面重点证明递推式。

证明

前置公式

组合恒等式：

二项式定理：

推导一：直接展开（理解用，）

从定义出发：

拆出一个 ，并使用组合恒等式：

令 ，注意 项为 ：

提出一个 ：

用二项式定理展开：

代回：

注意到：

于是：

推导二：关键递推（可实现）

再次从定义出发，使用组合拆分：

第一项即为 。

处理第二项，令 ：

展开 ：

于是得到：

拆出 项：

注意到恒等关系：

最终整理得：

最终结论

证毕。

与代码的对应关系（简述）

  • 数组 f[j] 表示
  • 每一层 更新本质是递推式
  • 初始值 f[0]=(x+1)^n 对应边界条件