Finite calculus
用红色标出来的是需要特别注意的地方。
差分与下降幂
定义差分算子
\[\Delta f=f(x+1)-f(x) \]定义 \(\mathbf{E}f=f(x+1)\)。
Thus
-
\(\Delta (u\pm v)=\Delta u\pm \Delta v\).
-
\(\Delta Cu=C\Delta u\) where \(C\) is a constant.
-
\(\Delta uv=\textcolor{red}{u\Delta v+\mathbf{E}v\Delta u}。\)对 \(m\ge 0\)
定义 \(x\) 的 \(m\) 次下降幂
\[x^{\underline{m}}=x(x-1)\cdots (x-m+1) \]和 \(m\) 次上升幂
\[x^{\overline{m}}=x(x+1)\cdots (x+m-1) \]（特别地，\(x^{\underline{0}}=x^{\overline{0}}=1\)）
注意到 \(n!=n^{\underline{n}}=1^{\overline{n}}\)。
那么对于指数为负的情况捏？
对于下降幂，我们注意到
\[x^{\underline{m}}=(x-m+1)x^{\underline{m-1}} \]于是
\(x^{\underline{0}}=(x+1)x^{\underline{-1}}\)
\(x^{\underline{-1}}=(x+2)x^{\underline{-2}}\)
不难推出
\(\displaystyle x^{\underline{-1}}=\frac{1}{x+1}, x^{\underline{-2}}=\frac{1}{(x+1)(x+2)}\)
于是我们可以扩充下降幂的定义
\[x^{\underline{m}}=\begin{cases} x(x-1)\cdots(x-m+1), & m\gt 0 \\ 1, & m=0 \\ \displaystyle\frac{1}{(x+1)(x+2)\cdots(x+(-m))} & m\lt 0 \end{cases} \]注意到
\[x^{\underline{-m}}=\frac{1}{(x+m)^{\underline{m}}} \]对于下降幂，我们有很好的性质
\[\Delta x^{\underline{n}}=nx^{\underline{n-1}} \]证明：
\[\begin{aligned} \Delta x^{\underline{n}}&=(x+1)x(x-1)\cdots (x-n+2)-x(x-1)\cdots(x-n+1) \\ &=[x+1-(x-n+1)]x(x-1)\cdots (x-n+2) \\ &=nx^{\underline{n-1}} \end{aligned} \]证毕。
定和式与不定和式
我们定义定和式
\[{\sum}_{a}^{b} f(x)\delta x=\sum_{i=a}^{\textcolor{red}{b-1}} f(i) \]类比无限微积分中的
\[\int_a^b \mathrm{d}f(x)=f(b)-f(a) \]于是我们有
\[{\sum}_{a}^{b} \Delta f(x)\delta x=f(b)-f(a) \]类似的，可以定义不定和式。具体地，若 \(f=\Delta F\)，则 \(\sum f=F+C\)（其中 \(C\) 为常量）
我们立刻可以得到
-
\(\displaystyle {\sum}_a^a f(x)\delta x=0\)
-
\(\displaystyle {\sum}_a^b f(x)\delta x=-{\sum}_b^a f(x)\delta x\)
-
\(\displaystyle {\sum}_a^b f(x)\delta x+{\sum}_b^c f(x)\delta x={\sum}_a^c f(x)\delta x\)
-
\(\displaystyle {\sum}_a^b (f(x)+g(x))\delta x={\sum}_a^b f(x)\delta x+{\sum}_a^b g(x)\delta x\)
-
\(\displaystyle {\sum}_a^b Cf(x)\delta x=C{\sum}_a^b f(x)\delta x\)
例 1
求出
\[\sum_{i=0}^{n-1} a^i \quad (a\neq 1) \]我们有 \(\Delta a^x=a^{x+1}-a^x=(a-1)a^x\)。
于是 \(\displaystyle a^x=\Delta\left(\frac{a^x}{a-1}\right)\)。
代入可以得到
\[\sum_{i=0}^{n-1} a^i={\sum}_{0}^n \Delta\left(\frac{a^x}{a-1}\right)\delta x=\frac{a^n-1}{a-1} \]例 2
计算
\[\sum_{i=1}^{n} i^2 \]注意到 \(x^2=x^{\underline{2}}+x^{\underline{1}}\)，而且 \(x^{\underline{2}}=\Delta \frac{1}{3}x^{\underline{3}},x^{\underline{1}}=\Delta \frac{1}{2}x^{\underline{2}}\)。
于是
\[\begin{aligned} \sum_{i=1}^{n} i^2&=\sum_{i=0}^{n} (i^{\underline{2}}+i^{\underline{1}})\\ &={\sum}_{0}^{n+1} (\Delta \frac{1}{3}x^{\underline{3}}+\Delta \frac{1}{2}x^{\underline{2}}) \\ &=\left[\frac{1}{3}x^{\underline{3}}+\frac{1}{2}x^{\underline{2}}\right]\bigg|_{0}^{n+1}\\ &=\frac{1}{3}(n+1)(n)(n-1)+\frac{1}{2}n(n+1)\\ &=\frac{1}{6}n(n+1)(2n+1) \end{aligned} \]P1625 求和
求出
\[\sum_{i=1}^n \frac{1}{\prod_{j=i}^{i+m-1}j} \]其中 \(n+m\leq 500,n\gt 0,m\gt 1\)。
\[\begin{aligned} \sum_{i=1}^n \frac{1}{\prod_{j=i}^{i+m-1}j}&= \sum_{i=0}^{n-1} \frac{1}{\prod_{j=i+1}^{i+m}j} \\ &=\sum_{i=0}^{n-1} \frac{1}{(i+m)(i+m-1)\cdots (i+1)} \\ &=\sum_{i=0}^{n-1} i^{\underline{-m}} \\ &={\sum}_0^n \Delta\left(\frac{x^{\underline{1-m}}}{1-m}\right)\delta x \\ &=\frac{n^{\underline{1-m}}-0^{\underline{1-m}}}{1-m} \\ &=\frac{\frac{1}{(m-1)(m-2)\cdots 1}-\frac{1}{(n+1)(n+2)\cdots (n+m-1)}}{m-1} \\ &=\frac{\frac{(n-m+1)(n-m)\cdots m}{(n+m-1)!}-\frac{n!}{(n+m-1)!}}{m-1} \\ &=\frac{(n+m-1)^{\underline{n}}-n!}{(m-1)(n+m-1)!} \end{aligned} \]例 3
求证：
\[\sum_{i=0}^{n} {i\choose m}={n+1 \choose m+1} \]（上指标求和）
我们有 \(\displaystyle {n\choose k}=\frac{n^{\underline{k}}}{k!}\)
于是
\[\begin{aligned} \sum_{i=0}^n {i\choose m}&=\sum_{i=0}^{n}\frac{i^{\underline{m}}}{m!} \\ &=\frac{1}{m!}{\sum}_0^{n+1} \Delta \frac{x^{\underline{m+1}}}{m+1} \delta x \\ &=\frac{1}{m!}\frac{(n+1)^{\underline{m+1}}}{m+1} \\ &=\frac{(n+1)^{\underline{m+1}}}{(m+1)}! \\ &={n+1\choose m+1} \end{aligned} \]现在将有限和无限积分表对照如下。
| $f $ | \(\sum f\) | \(f\) | \(\displaystyle \int f\) |
|---|---|---|---|
| \(x^{\underline{n}}\) | \(\displaystyle \frac{x^{\underline{n+1}}}{n+1}\) | \(x^n\) | \(\displaystyle \frac{x^{n+1}}{n+1}\) |
| \(2^x\) | \(2^x\) | \(\mathrm{e}^x\) | \(\mathrm{e}^x\) |
| \(a^x\) | \(\displaystyle \frac{a^x}{a-1}\) | \(a^x\) | \(a^x\ln a\) |
Stirling 数与下降幂
我们知道，下降幂在有限微积分中担当起了无限微积分中幂函数的职责。但是我们常见的是幂函数，我们需要将幂函数转为下降幂。
我们有
\[x^n=\sum_{k=0}^n {n\brace k} x^{\underline{k}} \]\[x^{\underline{n}}=\sum_{k=0}^{n} {n\brack k}(-1)^{n-k} x^k \]其中 \(\displaystyle {n\brace k}\) 表示第二类 Stirling 数，即将 \(n\) 个元素分进 \(k\) 个集合（不计集合的顺序）的方案数，\(\displaystyle {n\brack k}\) 表示第一类 Stirling 数，即将 \(n\) 个元素分进 \(k\) 个环里（不计环的顺序）的方案数。
由此我们得到 \(1\sim n\) 的 \(k\) 次幂和的公式。
\[\begin{aligned} \sum_{i=0}^{n} i^k&=\sum_{i=0}^n\sum_{j=0}^{k}{k\brace j} i^{\underline{j}} \\ &=\sum_{j=0}^k {k\brace j}\sum_{i=0}^{n} i^{\underline{j}} \\ &=\sum_{j=0}^k {k\brace j}{\sum}_{0}^{n+1} \Delta \frac{x^{\underline{j+1}}}{j+1} \delta x\\ &=\sum_{j=0}^k {k\brace j}\frac{(n+1)^{\underline{j+1}}}{j+1} \end{aligned} \]P4948 数列求和
求
\[\sum_{i=1}^n i^k a^i \]其中 \(n\leq 10^{18}\)，\(k\leq 2\times 10^3\)。
\[\begin{aligned} \sum_{i=1}^n i^k a^i&=\sum_{i=1}^na^i\sum_{j=0}^k {k\brace j}i^{\underline{j}} \\ &=\sum_{j=0}^{k} {k\brace j}\sum_{i=1}^n a^ii^{\underline{j}} \\ &=\sum_{j=0}^{k} {k\brace j}{\sum}_1^{n+1}a^xx^{\underline{j}}\delta x \end{aligned} \]进行分类讨论。
- \(a=1\)
预处理 \(\Theta(k^2)\) 或 \(\Theta(k\log k)\)，递推计算是 \(\Theta(k)\) 的。
- \(a\neq 1\)
我们有
\[\Delta uv=u\Delta v+\mathbf{E}v\Delta u \]两边同时求和，得
\[uv=\sum u\Delta v\delta x+\sum\mathbf{E}v\Delta u\delta x \]即
\[\sum u\Delta v\delta x=uv-\sum\mathbf{E}v\Delta u\delta x \]考虑求出 \(a^xx^{\underline{j}}\) 的“原和式”（不定和式）。我们不妨令 \(u=a^x\)，\(\Delta v=x^{\underline{j}}\)（则 \(v=\dfrac{x^{\underline{j+1}}}{j+1}\)）
于是 \(\sum a^xx^j\delta x=\dfrac{a^xx^{\underline{j+1}}}{j+1}-\sum (x+1)^{\underline{j}}(a-1)a^x\delta x\)
好像不可做。如果令 \(u=x^{\underline{j}}\)，\(\Delta v=a^x\)（则 \(v=\dfrac{a^x}{a-1}\)）呢？
代入得到
\(\sum a^xx^j\delta x=\dfrac{a^xx^{\underline{j}}}{a-1}-\sum \dfrac{a^{x+1}}{a-1}jx^{\underline{j-1}}\delta x\)
也就是说
\[{\sum}_0^{n+1} a^xx^j=\frac{a^xx^j}{a-1}\bigg|_{0}^{n+1}-\frac{j\cdot a}{a-1}{\sum}_0^{n+1} a^xx^{\underline{j-1}}\delta x \]边界为 \(j=0\) 时，\(\sum a^xx^j\delta x=\sum a^x\delta x=\dfrac{a^x}{a-1}\)。
预处理 \(\Theta(k^2)\) 或 \(\Theta(k\log k)\)，递推计算是 \(\Theta(k)\) 的。
综上，我们在 \(\Theta(k^2)\) 或 \(\Theta(k\log k)\) 的复杂度内解决了本题。
类比于无限微积分中高阶导数的概念，我们在有限微积分中也有高阶差分。
我们可以定义 \(f\) 的 \(n\) 阶差分
\[\Delta^n f= \begin{cases} f, & n=0 \\ \Delta(\Delta^{n-1} f) & n\gt 0 \end{cases} \]我们注意到
\[\mathbf{E}f=f(x+1) \]\[\Delta f=f(x+1)-f(x) \]所以我们不难得到 \(\Delta=\mathbf{E}-1\)。
于是我们有
\[\Delta^n f=(\mathbf{E}-1)^n f=\sum_{k=0}^n {n\choose k}(-1)^{n-k}\mathbf{E}^k f \]\(\mathbf{E}^k\) 类似 \(\Delta^k\) 递归地定义。
P5907 数列求和加强版 / SPOJ MOON4
求
\[\sum_{i=1}^n i^k a^i \]其中 \(\boldsymbol{k\leq 10^7}\)。
设 \(\displaystyle f(n)={\sum}_0^n x^ka^x\delta x\)，答案即为 \(f(n+1)-f(1)\)。
注意到在普通版中我们有
\[\begin{aligned} \sum a^xx^k\delta x&=\dfrac{\textcolor{red}{a^x}x^{\underline{k}}}{a-1}-\frac{a\cdot k}{a-1}\textcolor{red}{a^{x}}\sum x^{\underline{k-1}}\delta x \\ &=a^x\left(\frac{x^{\underline{k}}}{a-1}-\frac{a\cdot k}{a-1}\sum x^{\underline{k-1}}\right) \end{aligned} \]\(a^x\) 右边的那一包东西显然是一个 \(k\) 次多项式，不妨设为 \(g(x)\)。则我们有
\[{\sum}_l^r a^xx^k\delta x=a^rg(r)-a^lg(l) \]则
\[f(n)=a^ng(n)-a^0g(0) \]如果我们能知道 \(g(0),g(1),\cdots,g(n)\) 的点值，就不难应用 Lagrange 插值法在 \(\Theta(k)\) 内求出 \(g(n+1)\)。那么问题转化为如何求 \(g(0),g(1),\cdots,g(n)\)。
我们考虑到
\[f(n)=a^ng(n)-a^0g(0) \]即
\[g(n)=\frac{f(n)+g(0)}{a^{n}} \]\(f(0),f(1),\cdots,f(k)\) 可以 \(\Theta(k)\) 递推。那么现在的当务之急就是求出 \(g(0)\) 了。
我们知道 \(\deg g=k\)，这意味着 \(\Delta^{k+1} g=0\)。
于是
\[\sum_{i=0}^{k+1}{k+1\choose i}(-1)^{k+1-i}\mathbf{E}^{i}g(0)=0 \\ \sum_{i=0}^{k+1}{k+1\choose i}(-1)^{k+1-i}g(i)=0 \\ \sum_{i=0}^{k+1}{k+1\choose i}(-1)^{k+1-i}a^{-i}[f(i)+g(0)]=0 \\ \sum_{i=0}^{k+1}{k+1\choose i}(-1)^{k+1-i}a^{-i}f(i)+\sum_{i=0}^{k+1}{k+1\choose i}(-1)^{k+1-i}a^{-i}g(0)=0 \\ \sum_{i=0}^{k+1}{k+1\choose i}(-1)^{k+1-i}a^{-i}f(i)+(a^{-1}-1)^{k+1}g(0)=0 \\ g(0)=-\frac{1}{a^{-1}-1}\sum_{i=0}^{k+1}{k+1\choose i}(-1)^{k+1-i}a^{-i}f(i) \]不难 \(\Theta(k)\) 求出。综上我们在 \(\Theta(k)\) 的时间复杂度内解决了本题。
P5349 幂
给定 \(m\) 次多项式 \(f\) 和有理数 \(r\in (0,1)\)，求
\[\sum_{n=0}^{+\infty} f(n)r^n \]模 \(998,422,353\)。其中 \(m\leq 10^5\)。多项式以系数形式给出。
考虑对于单项式怎么做。
也就是求
\[\begin{aligned} \sum_{n=0}^{+\infty} n^kr^n &= \dfrac{r^nn^{\underline{k}}}{r-1}-\sum \dfrac{r^{n+1}}{r-1}kn^{\underline{k-1}}\delta \end{aligned} \]