$k$ 阶前缀和公式

前缀和

对于序列 $a$ ，它的前缀和定义为满足以下条件的序列 $S$ 。

$$S_n = \sum_{1\le i \le n}a_i$$

特别地，我们通常定义 $S_0=0$ ，但是在本文中不考虑。

---

$k$ 阶前缀和

定义函数 $f : a \to S$ 为序列 $a$ 到它的前缀和 $S$ 的映射。

则序列 $a$ 的 $k$ 阶前缀和为 $f^k(a)~(k \ge 1)$ 。通俗地说，就是对 $a$ 做了 $k$ 次前缀和。

---

$k$ 阶前缀和公式

记序列 $a$ 的 $k$ 阶前缀和为 $S_k$ ，$S_k$ 的第 $i$ 项为 $S_{k,i}$ ，则

$$S_{k,i} = \sum_{1 \le j \le i} \binom{k + i - j - 1}{k-1}a_j$$

证明：

考虑一个元素 $x$ 在位置 $1$ 时对第 $i$ 次前缀和的贡献。

设 $f_{i,j}$ 表示第 $i$ 次前缀和的第 $j$ 项的系数，则有

$$f_{i,j} = f_{i-1,j} + f_{i,j-1}$$

边界：$f_{1,j} = 1$ 。

对于这种看上去很经典的二元递推式，我们考虑它的其他意义。

则 $f_{n,m}$ 就是在网格图中，从 $(1,1)$ 走到 $(n,m)$ ，每步只能向下或向右走的方案数

显然我们要走 $n+m-2$ 步，其中 $m-1$ 步向右，则方案数为 $\binom{n+m-2}{m-1}$ ，即

$$f_{n,m} = \binom{n+m-2}{m-1}$$

考虑一般的情况，当 $x$ 在位置 $p$ 的时候，递推式不变，但边界变为 $f^{\prime}_{1,j} = [j \ge p]$

因此问题就变为了从 $(1,p)$ 走到 $(n,m)$ 的方案数，或者 $(1,1)$ 走到 $(n,m-p+1)$ 的方案数，则

$$f^{\prime}_{n,m} = \binom{n + m - p - 1}{m-p} = \binom{n + m - p - 1}{n-1}$$

综上，第 $k$ 次前缀和的第 $i$ 项为

$$S_{k,i} = \sum_{1 \le j \le i} \binom{k + i - j - 1}{k-1}a_j$$

证毕。$\square$

---

参考文献：

[1] https://blog.csdn.net/eternity19/article/details/119735293