溫馨提示: 本文文檔大小約\(11KB\).

引入

自然數(shù)冪和是一個(gè)我們從小就耳熟能詳?shù)慕?jīng)典問題。定義\(S(n,k)=\sum^{n}_{i=0} i^k\), 顯然\(S(n,k)\)為關(guān)于\(n\)的不超過\((k+1)\)次多項(xiàng)式，那么給定\(k\), 如何快速求出這個(gè)多項(xiàng)式的系數(shù)？或者給定\(n\)和\(k\), 如何快速求出\(S(n,k)\)? 這就是本文的討論內(nèi)容。

本文介紹三種不同的方法——拉格朗日插值法、第二類斯特林?jǐn)?shù)法和伯努利數(shù)法，這三種方法在解決不同的問題上各有優(yōu)劣。

符號(hào)約定

\(x^{\underline n}\)表示\(x\)的\(n\)次下降冪，即\(x^{\underline n}=\prod^{n}_{i=1}(x-i+1)\).

本文中提到的所有\(i\), 與虛數(shù)均無關(guān)系。

本文中所有運(yùn)用數(shù)學(xué)歸納法進(jìn)行證明的定理，歸納奠基均省略，請(qǐng)讀者自行處理。

拉格朗日(Lagrange)插值法

概述

Lagrange插值法的應(yīng)用范圍很廣，給定任意\((n+1)\)個(gè)互不相同的點(diǎn)值\((x_i,y_i)\) (\(i=0,1,...,n\))，其可以在\(O(n^2)\)時(shí)間內(nèi)求出一個(gè)不超過\(n\)次的多項(xiàng)式\(f(x)\)，滿足對(duì)于任意\(i\), \(f(x_i)=y_i\). (“互不相同”指對(duì)于任意\(0\le i<j\le n\)有\(x_i\ne x_j\))

暴力做法

設(shè)\(f(x_i)=\sum^{n}_{i=0} a_ix^i\). 根據(jù)\((n+1)\)個(gè)點(diǎn)值，我們可以列出\((n+1)\)個(gè)方程，第\(j\)個(gè)形如\(\sum^{n}_{i=0}x_j^ia_i=y_j\).

直接高斯消元求解，時(shí)間復(fù)雜度\(O(n^3)\).

插值多項(xiàng)式的唯一性

定理1 給定任意\((n+1)\)對(duì)互不相同的點(diǎn)值\((x_i,y_i)\)，恰好存在一個(gè)不超過\(n\)次的多項(xiàng)式\(f(x)\)，滿足對(duì)于任意\(i\), \(f(x_i)=y_i\).

證明 根據(jù)暴力做法，我們就是要證明方程左邊的\((n+1)\times (n+1)\)的系數(shù)矩陣可逆。

實(shí)際上系數(shù)矩陣就是著名的范德蒙德(Vandermonde)矩陣: \(\begin{bmatrix} 1&1&1&...&1\\ a_0&a_1&a_2&...&a_n\\ a_0^2&a_1^2&a_2^2&...&a_n^2\\ & & & ... & \\ a_0^n&a_1^n&a_2^n&...&a_n^n\end{bmatrix}\)

可以證明，該矩陣行列式為\(\prod_{0\le i<j\le n} (a_j-a_i)\).

考慮數(shù)學(xué)歸納法，自下而上每一行減去上一行的\(a_0\)倍，該矩陣變?yōu)?span id="ze8trgl8bvbq" class="math display">\[\begin{bmatrix}1&1&1&...&1\\ 0&a_1-a_0&a_2-a_0&...&a_n-a_0\\ 0&a_1(a_1-a_0)&a_2(a_2-a_0)&...&a_n(a_n-a_0)\\&&&...&\\0&a_1^{n-1}(a_1-a_0)&a_2^{n-1}(a_2-a_0)&...&a_n^{n-1}(a_n-a_0)\end{bmatrix}\]

然后對(duì)第一列展開，每一行提取公因式之后可得\(|V|=|V'|\prod^{n}_{i=1}(a_i-a_0)\), 其中\[V'=\begin{bmatrix}1&1&...&1\\a_1&a_2&...&a_n\\a_1^2&a_2^2&...&a_n^2\\&&...&\\a_1^{n-1}&a_2^{n-1}&...&a_n^{n-1}\end{bmatrix}\]

是一個(gè)\(n\times n\)的Vandermonde矩陣，由歸納知其行列式為\(\prod_{1\le i<j\le n}(a_j-a_i)\), 故\(|V|=\prod_{0\le i<j\le n}(a_j-a_i)\), 證畢。

由上可知，由于任意\(1\le i<j\le n\)滿足\(a_i\ne a_j\), 故該矩陣行列式不為\(0\).

任意多項(xiàng)式的插值

直接給出公式。

定理2 符合\((n+1)\)個(gè)點(diǎn)值\((x_i,y_i)\)的多項(xiàng)式為\(f(x)=\sum^{n}_{i=0} y_i\prod_{0\le j\le n,j\ne i}\frac{x-x_j}{x_i-x_j}\).

證明 代入\(x_k\), 當(dāng)\(i\ne k\)時(shí)后面的乘法有一項(xiàng)因數(shù)是\(x-x_k=0\), 故該積恒為\(0\). 當(dāng)\(i=k\)時(shí)顯然值為\(y_i\). 因此該多項(xiàng)式符合\((n+1)\)個(gè)給定點(diǎn)值。

至于這個(gè)公式具體是怎么推出來的，大概是考慮求Vandermonde矩陣的逆矩陣，使用矩陣分塊法解決，此處不再贅述。

有了這個(gè)公式，我們可以先預(yù)處理出\(\prod^n_{i=0}(x-x_i)\)的每一項(xiàng)系數(shù)(這是一個(gè)\((n+1)\)次多項(xiàng)式)，然后對(duì)于每個(gè)\(i\)暴力用這個(gè)多項(xiàng)式除以\((x-x_i)\). 由于多項(xiàng)式除以一次式可在\(O(n)\)時(shí)間內(nèi)完成，該算法時(shí)間復(fù)雜度為\(O(n^2)\).

使用FFT最好可以做到\(O(n\log ^2n)\), 但是我不會(huì)。

那么對(duì)于自然數(shù)冪和問題，我們可以求出\(S(m,n)\)在\(0,1,2,...,n\)處的點(diǎn)值，然后利用Lagrange插值求出這個(gè)\((n+1)\)次多項(xiàng)式的每一項(xiàng)系數(shù)，時(shí)間復(fù)雜度\(O(n^2)\). 如果給定一個(gè)\(m\)要求\(S(m,n)\)的值，那么可以直接把\(n\)代入多項(xiàng)式求值，時(shí)間復(fù)雜度\(O(n^2)\), 與\(m\)無關(guān)。

對(duì)于自然數(shù)冪和問題的優(yōu)化

如果給定\(m,n\)要求\(S(m,n)\), 不需要求出多項(xiàng)式每一項(xiàng)的系數(shù)，是否可以做到更優(yōu)的復(fù)雜度？(假設(shè)\(n>k\))

\(f(n)=\sum^{m}_{i=0}y_i\prod_{0\le j\le n, j\ne i}\frac{n-j}{i-j}=\sum^{m}_{i=0}y_i\frac{\prod_{0\le j\le n}(m-j)}{\prod_{0\le j\le n,j\ne i}(i-j)\times (m-i)}\), 可以用階乘和逆元之類的方法優(yōu)化，時(shí)間復(fù)雜度\(O(n\log n)\).

第二類斯特林(Stirling)數(shù)法

概述

第二類斯特林?jǐn)?shù)是一類重要的計(jì)數(shù)序列，又稱“斯特林子集數(shù)”，其定義為\(\begin{Bmatrix}n\\k\end{Bmatrix}\)表示將\(n\)個(gè)有編號(hào)的物品放入\(k\)個(gè)無編號(hào)的集合中，每個(gè)集合都非空的方案數(shù)。

由定義可以得出其遞推式: \(\begin{Bmatrix}n\\k\end{Bmatrix}=k\begin{Bmatrix}n-1\\k\end{Bmatrix}+\begin{Bmatrix}n-1\\k-1\end{Bmatrix}\). 考慮最后一個(gè)物品，如果將其單獨(dú)放入一個(gè)集合中，則方案數(shù)為\(\begin{Bmatrix}n-1\\k-1\end{Bmatrix}\), 否則所有集合都已經(jīng)有元素了，所以要加以區(qū)分，放入不同的集合算不同的方案，方案數(shù)為\(k\begin{Bmatrix} n-1\\k\end{Bmatrix}\).

下面兩個(gè)重要公式給出了第二類Stirling數(shù)與冪運(yùn)算之間的關(guān)系。

定理3 \(m^n=\sum^{n}_{i=0} \begin{Bmatrix}n\\i\end{Bmatrix}m^{\underline i}\).

證明 我們可以從代數(shù)和組合等不同角度來證明。

證法一 代數(shù)做法: 考慮使用數(shù)學(xué)歸納法。對(duì)\(n\)施歸納，\[m^{n+1}=\sum^{n}_{i=0}m\begin{Bmatrix}n\\i\end{Bmatrix}m^{\underline i}\\ =\sum^{n}_{i=0}(m-i)\begin{Bmatrix}n\\i\end{Bmatrix}m^{\underline i}+\sum^{n}_{i=0}i\begin{Bmatrix}n\\i\end{Bmatrix}m^{\underline i}\\ =\sum^{n}_{i=0}\begin{Bmatrix}n\\i\end{Bmatrix}m^{i+1}+\sum^{n}_{i=0}i\begin{Bmatrix}n\\i\end{Bmatrix}m^{\underline i}\\ =\sum^{n+1}_{i=1}\begin{Bmatrix}n\\i-1\end{Bmatrix}m^{\underline i}+\sum^{n}_{i=0}i\begin{Bmatrix}n\\i\end{Bmatrix}m^{\underline i}\\ =\sum^{n+1}_{i=0}\begin{Bmatrix}n+1\\i\end{Bmatrix}m^{\underline i}\]

證法二 組合做法: \(m^n\)相當(dāng)于把\(n\)個(gè)有標(biāo)號(hào)數(shù)放入\(m\)個(gè)有標(biāo)號(hào)集合的方案數(shù)。這些集合有的是空集，有的是非空集合，考慮枚舉有多少個(gè)非空集合，先從有標(biāo)號(hào)集合里有順序地選出這\(i\)個(gè)非空集合(方案數(shù)\(m^{\underline i}\)), 再計(jì)算\(n\)個(gè)數(shù)放進(jìn)去的方案數(shù)。

定理4 \(\begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}\sum^{m}_{i=0}(-1)^i\begin{pmatrix}m\\i\end{pmatrix}(m-i)^n\)

證明 組合意義上相當(dāng)于上式套容斥，代數(shù)意義上相當(dāng)于上式套二項(xiàng)式反演。

根據(jù)定理4，我們發(fā)現(xiàn)固定\(n\)之后可以用FFT在\(O(n\log n)\)時(shí)間內(nèi)對(duì)每個(gè)\(m\)求出第二類斯特林?jǐn)?shù)。

分別構(gòu)造多項(xiàng)式\(F(x)=\sum_{i\ge 0}\frac{(-1)^i}{i!}x^i\)與\(G(x)=\sum_{i\ge 0}\frac{i^n}{i!}x^i\), 卷積相乘即可。

利用第二類斯特林?jǐn)?shù)求自然數(shù)冪和

定理4指出一種快速求第二類斯特林?jǐn)?shù)的方法，而定理3指出第二類斯特林?jǐn)?shù)與自然數(shù)的冪的聯(lián)系。

既然定理3的式子是把通常冪轉(zhuǎn)化為下降冪，那么求自然數(shù)下降冪的和是否容易一些呢？

這是一個(gè)小學(xué)數(shù)學(xué)問題。\[\sum^{m}_{i=0}i^{\underline n}=\frac{1}{n+1}\sum^{m}_{i=0}(i+1)^{\underline {n+1}}-i^\underline {n+1}=\frac{(m+1)^{\underline {n+1}}-0^{\underline {n+1}}}{n+1}=\frac{1}{n+1}(m+1)^{\underline {n+1}}\]

那么考慮將自然數(shù)冪和轉(zhuǎn)化為自然數(shù)下降冪和: \[S(m,n)=\sum^{m}_{i=0}i^n=\sum^{m}_{i=0}\sum^{n}_{j=0}\begin{Bmatrix}n\\j\end{Bmatrix}i^{\underline j}=\sum^{n}_{j=0}\begin{Bmatrix}n\\j\end{Bmatrix}\sum^{m}_{i=0}i^{\underline j}=\sum^{n}_{j=0}\frac{1}{j+1}\begin{Bmatrix}n\\j\end{Bmatrix}(m+1)^{\underline {j+1}}\].

于是我們得到了一種通過第二類斯特林?jǐn)?shù)求自然數(shù)冪和的方法。如果\(n\)不固定，那么可以\(O(n^2)\)預(yù)處理第二類斯特林?jǐn)?shù)；如果\(n\)固定，那么可以\(O(n\log n)\)求第二類斯特林?jǐn)?shù)一整行。求出第二類斯特林?jǐn)?shù)之后，可以在不超過\(O(n\log P)\)的時(shí)間復(fù)雜度內(nèi)求出\(S(m,n)\), 其中\(P\)為模數(shù)，\(O(\log P)\)為求乘法逆元的復(fù)雜度。

特別地，如果模數(shù)性質(zhì)不好，沒法求逆元怎么辦？此時(shí)Lagrange插值法失去了用武之地，而該方法依然可用，但時(shí)間復(fù)雜度退化為\(O(n^2)\). 我們只需要求\((j+1)\)的逆元，而\((m+1)^{\underline {j+1}}\)是把\((j+1)\)個(gè)連續(xù)整數(shù)相乘，肯定有一個(gè)是\((j+1)\)的倍數(shù)，每次找到那個(gè)倍數(shù)即可。

伯努利(Bernoulli)數(shù)法

注意在這一部分中，我們需要改變\(S(m,n)\)的定義。現(xiàn)在\(S(m,n)\)定義為\(\sum^{m-1}_{i=0}i^n\), 即比原來少了\(m^n\).

概述

伯努利數(shù)法與上面兩種方法的適用對(duì)象有所不同。伯努利數(shù)法適用于對(duì)于某個(gè)固定的\(m\), 以及\(1\)到\(N\)內(nèi)的所有的\(n\), 求出\(S(m,n)\)的值, 時(shí)間復(fù)雜度可以做到\(O(n\log n)\).

伯努利數(shù)本身就是由伯努利觀察自然數(shù)冪和的過程中發(fā)現(xiàn)的。他對(duì)于較小的\(n\)求出了\(S(m,n)\)多項(xiàng)式的每一次項(xiàng)的系數(shù)，然后發(fā)現(xiàn)\((n+1)\)次系數(shù)總是\(1\), 對(duì)于\(0\le k\le n\), \((n-k)\)次項(xiàng)系數(shù)總是等于一個(gè)常數(shù)乘以\(n\)的一個(gè)下降冪。于是他定義了伯努利數(shù)。

伯努利數(shù)\(B_n\)由以下遞歸關(guān)系定義: \(\sum^{n}_{i=0}{n+1\choose i}B_i=[n=0]\). 伯努利數(shù)的前\(5\)項(xiàng)是: \(B_0=0, B_1=-\frac{1}{2},B_2=\frac{1}{6},B_3=0,B_4=-\frac{1}{30},B_5=0\).

定理5 伯努利數(shù)的指數(shù)生成函數(shù)(EGF)為\(B(x)=\sum_{n\ge 0}\frac{B_n}{n!}=\frac{x}{e^x-1}\).

證明 \[\sum^{n}_{i=0}{n+1\choose i}B_i=[n=0]\\\sum^{n+1}_{i=0}{n+1\choose i}B_i=B_{n+1}+{n=0}\\\sum^{n}_{i=0}{n\choose i}B_i=B_n+[n=1]\\\frac{B_n}{n!}+[n=1]=\sum^{n}_{i=0}\frac{1}{(n-i)!}\frac{B_i}{i!}\\B(x)+x=B(x)e^x\\B(x)=\frac{x}{e^x-1}\]

由此，用FFT多項(xiàng)式求逆就可以在\(O(n\log n)\)時(shí)間內(nèi)預(yù)處理伯努利數(shù)前\(n\)項(xiàng)。

利用伯努利數(shù)求自然數(shù)冪和

定理6 伯努利數(shù)滿足關(guān)系式\(S(m,n)=\frac{1}{n+1}\sum^{n}_{i=0}{n+1\choose i}B_im^{n+1-i}\).

證明 考慮固定\(m\), 寫出\(S(m,n)\)的指數(shù)生成函數(shù)\(S_m(x)\).

\[S_m(x)=\sum_{n\ge 0}S(m,n)\frac{x^n}{n!}\\ =\sum_{n\ge 0}\sum^{m-1}_{i=0}i^n\frac{x^n}{n!}\\=\sum^{m-1}_{i=0}\sum_{n\ge 0}\frac{i^n}{n!}x^n\\=\sum^{m-1}_{i=0}e^{ix}\\=\frac{e^{mx}-1}{e^x-1}\\=B(x)\frac{e^{mx}-1}{x}\\=B(x)\sum_{n\ge 0}\frac{m^{n+1}}{(n+1)!}x^n\\ [x^n]S_m(x)=\sum^{n}_{i=0}\frac{B_i}{i!}\frac{m^{n+1-i}}{(n+1-i)!}\]

然后由于是指數(shù)生成函數(shù)所以\(S(m,n)=n![x^n]S_m(x)\), 證畢。

那么，我們用與上面幾例類似的方法，可以用FFT在\(O(N\log N)\)時(shí)間內(nèi)對(duì)固定的\(m\)和每個(gè)\(n=1,2,...,N\)求出\(S(m,n)\).

三種方法的比較

三種方法適用的問題形式不同，各自的效率也有優(yōu)劣。

當(dāng)數(shù)據(jù)范圍可以接受\(O(n^2)\)的時(shí)間復(fù)雜度時(shí)，三種做法都可以不用FFT實(shí)現(xiàn)，代碼難度都較小。

求出多項(xiàng)式的每一次項(xiàng)系數(shù)，這是Lagrange插值法的專長(zhǎng)。

當(dāng)固定\(n\)不固定\(m\)時(shí)，Lagrange插值法和第二類Stirling數(shù)法較為適用。

當(dāng)固定\(m\)不固定\(n\)時(shí)，Bernoulli數(shù)法較為適用。

當(dāng)模數(shù)性質(zhì)不好無法求逆元時(shí)，Stirling數(shù)法是較好的選擇。

解決有關(guān)具體問題時(shí)，一定要注意具體的限制(比如詢問形式、詢問次數(shù)、\(n,m\)的大小、是否固定)，選擇較好的方法。

總結(jié)

以上是生活随笔為你收集整理的【学习笔记】自然数幂和的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。