\(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