小議一類數列求和

上篇文章反響不太好啊QAQ大佬都說太水，人民羣眾又說太沒意思了QAQQAQ不過我會儘力寫出更水的內容的！

也是挺常見的問題，我們會求，那麼針對因子來說，更高次數的呢？有沒有什麼快速處理的方法？

摘要介紹了一道針對一類和式的演算法題，並使用多種方法完成了對其的求和。

Description

考慮求

$sum_{i=0}^n i^kcdot q^i,nin mathbb N,qinmathbb R-{0,1}$

Analysis

我們首先記它為。

特殊情形

就不說了，我們看一下的情形。

當然是招牌（套路）擾動法，有

$egin{aligned} (n+1)^2cdot q^{n+1}+S_2(n) &=sum_{i=0}^{n}(i+1)^2cdot q^{i+1}\ &=qsum_{i=0}^nleft[ (i^2+2i+1)q^i ight]\ &=qS_2(n)+2qS_1(n)+qS_0(n) end{aligned}$

移項整理就有

$S_2(n)=frac{(n+1)^2cdot q^{n+1}-2qS_1(n)-qS_0(n)}{q-1}$

這裡給不瞭解怎麼擾動的同學捋一捋這裡是怎麼來的，會的巨佬可以跳過。

擾動法專題

擾動法是一種處理和式的技巧，通過將和式的最後一項和第一項分別寫出來，利用這兩種形式構造一個等式，以利用被求和式的本質結構特徵，這樣理論上就可以得到相關的性質。（但是並不能保證，只是這種技巧對於某些特定結構特別有效。）不妨先看一個簡單的例子。

$求 S_n=sum_{i=0}^n q^i的封閉形式\ egin{aligned} q^{n+1}+sum_{i=0}^nq^i &=1+sum_{i=1}^{n+1}q^i\ &=1+qsum_{i=0}^nq^i\ S_n+q^{n+1}&=qS_n+1 end{aligned} \ 移項整理得Sn=frac{1-q^{n+1}}{1-q}$

大體就都是這樣的步驟。

練習題 試使用擾動法求 $T(n)=sum_{i=0}^ni^2$ 。這題同上稍有不同，但只要注意總結和變通，也很好處理。

有了上面的基礎，做廣義的推廣可以說是非常簡單了。

$egin{aligned} (n+1)^kcdot q^{n+1}+S_k(n) &=sum_{i=0}^n(i+1)^kcdot q^{i+1}\ &=qsum_{i=0}^nleft[ q^isum_{j=0}^k inom{k}{j}i^j ight]\ &=qleft[ sum_{j=0}^k inom{k}{j}S_j(n) ight]\ &=qleft[ sum_{j=0}^{k-1} inom{k}{j}S_j(n) ight] + qS_k(n)\ end{aligned}$

$S_k(n)=frac{(n+1)^kcdot q^{n+1}-qleft[ sum_{j=0}^{k-1} inom{k}{j}S_j(n) ight]}{q-1} ag{1}$

和幾乎大同小異吧。這樣的話根據這個遞歸式我們可以求出答案。

另外還有錯位相減的做法（很親民啊）

$S_k(n)=sum_{i=0}^n i^kcdot q^i ag{2}=0+sum_{i=1}^{n}i^kcdot q^i$

$qS_k(n)=sum_{i=0}^{n} i^kcdot q^{i+1}=sum_{i=1}^{n+1} (i-1)^kcdot q^i=sum_{i=1}^n(i-1)^kcdot q^i+n^kcdot q^{n+1} ag{3}$

得

$(q-1)S_k(n)=n^kcdot q^{n+1}+sum_{i=1}^nleft[n^k-(n-1)^k ight]q^i$

$S_k(n)=frac{n^kcdot q^{n+1}+sum_{i=1}^nleft[n^k-(n-1)^k ight]q^i}{q-1} ag{4}$

我們容易發現，此時中括弧裏是一個次多項式，我們成功將這個問題規約成了規模更小的子問題。什麼？你擔心遞歸下去時多項式沒有這麼簡單、可能沒法繼續遞歸？實際上，一個平凡的結論是，對於任意次多項式，一定是次的，因為展開後和最高次項的係數一定是相同的，一減就減沒了。

下面是遞歸實現的完整代碼。

#include <cstdio> const int N = 2005, M = 1e9+7; typedef long long LL; LL n, a, k, m, l; LL dt[N], dw[N], inv, pa[N], pw;

inline LL qpow(LL x, LL y, LL ans = 1) {
for (; y; y>>=1, x = x * x % M)
if (y & 1) ans = ans * x % M;
return ans;
}

inline LL sub(LL x, LL y){
LL ans = x - y;
if(ans < 0) ans += M;
return ans;
}

inline LL cal(LL tk)
{
LL ans = sub(pw * dw[1] % M, pa[k - tk + 1] * dt[1] % M);
register LL i;
for(i = 1; i <= tk; i++) {
dt[i] = sub(dt[i + 1], dt[i]);
dw[i] = sub(dw[i], dw[i + 1]);
}
if(tk > 0) return ans = sub(ans, cal(tk - 1)) * inv % M;
return ans * inv % M;
}

int main()
{
register LL i, j;

scanf("%lld%lld%lld", &n, &a, &k);
for(i = 1, j = n, m = k + 1, pa[0] = 1; i <= m; i++, j--){
dt[i] = qpow(i, k);
dw[i] = qpow(j % M, k);
pa[i] = pa[i - 1] * a % M;
}
inv = qpow(a - 1, M - 2), pw = qpow(a, n + 1);
printf("%lld
", cal(k));

return 0;
}

接下來的內容可能難度會上一個檔次，不過都是很好懂的東西，只是正面想有些難度。

不知道你們做過一些關於具體的差比數列求和的題目沒有？

如果做過一些，你一定會注意到，答案總是可以整理成這樣的形式：

也就是說係數多項式常數項的相反數就是外面的常數，這個結論我們很好證明，因為我們有

$S_n=left[dfrac q{q-1}n-dfrac q{(q-1)^2} ight]cdot q^n+dfrac q{(q-1)^2}$

這個簡單的公式在此證明從略。

容易觀察出確實有這樣的關係，那麼對於高階差比數列是否也存在這個結論呢？答案是肯定的。

命題對於任意，存在使得

$S_k(n)=f(n)q^n-f(0) ag{5}$

證明乍一看無從下手，這個時候我們往往考慮使用數學歸納法（套路）。下文多項式的自變數默認為

首先，我們只需要對多項式證明即可（為什麼？），對於，我們已經證明。假設時都成立，那麼時考慮剛剛推出的式或式，因為這兩個式子都是線性的，隨手就能合併一下，這個結論由此得證。因細節較為繁瑣，在此不再贅述。但是給出對式歸納時應該構造這個函數：

$g(n)=frac1q[(q+1)f(n)-f(n-1)+i^n-i^{n-1}]$

這樣一來，我們知道了這個結論，就可以直接用上一篇文章中介紹的差分公式

$Delta^kf(n)=sum_{i=0}^kinom ki(-1)^{k-i}f(n+i)$

我們知道，是次多項式，所以次差分顯然為，這樣可以得到同的一個方程

$sum_{i=0}^{k+1}inom ki(-1)^{k-i+1}f(n+i)=0 ag{6}$

而之間有沒有關係呢？當然是有的，我們對式進行差分，就能得到的一個遞推式。

$egin{equation*} S_k(n)-S_k(n-1)=[f(n)-f(n-1)]cdot q^n\ n^kcdot q^n=[f(n)-f(n-1)]cdot q^n end{equation*}$

這樣，取前個遞推式與式聯立就可以解出所有未知數。不過要注意怎麼解，當然不是高斯消元……這裡都可以用線性表示，這樣一來就很好解了。那麼接下來就是求出多項式，從而得到了。既然這些點都知道了，那麼剩下的步驟當然是插值。

可以用拉氏插值，但那也太對不起我們上面的推導了（（（

所以還要引進一種先進無敵威力無窮的線性插值法，呃，這個，不要望文生義哈。這樣就可以在線性時間內完成這題了。

特殊多項式在整點上的線性插值方法?

blog.miskcoo.com

你以為這就完了嗎？

考慮多對數函數

${ m Li}_n(z)=sum_{i=1}^infty frac{z^i}{i^n}$

這是一個無窮級數。但是我們驚喜地發現

$sum_{i=1}^infty i^kcdot q^i={ m Li}_{-k}(q) ext{ when }|q|<1$

所以，要得到取其展開的前幾項即可。而剛剛的多項式，就在展開式中。

比如說，利用mma我們可以對小情形的給出

$egin{eqnarray} k=q=2& S(n)&=left(n^2-4cdot n+6 ight)cdot 2^n-6\ k=q=3& S(n)&=left(frac{4cdot n^3-18cdot n^2+36cdot n-33}{8} ight)cdot3^n+frac{33}{8}\ k=q=4& S(n)&=left(frac{27cdot n^4-144cdot n^3+360cdot n^2-528cdot n+380}{81} ight)cdot4^n-frac{380}{81}\ k=q=5& S(n)&=left(frac{128cdot n^5-800cdot n^4+2400cdot n^3-4600cdot n^2+5700cdot n-3535}{512} ight)cdot5^n +frac{3535}{512}\ end{eqnarray}$

這一是驗證了我們上面的結論，再一個是給出了這個序列。怎麼說呢？我們考察式，發現收斂時只剩下常數項，那麼多重對數給出的正是的值。

實際上還有這麼幾個恆等式，涉及到第二類斯特林數和歐拉數。

$displaystyle { m Li}_{-n}(z)=sum _{k=0}^{n}k!left{{n+1}atop{k+1} ight}left({z over {1-z}} ight)^{k+1}\ { m Li}_{-n}(z)=sum _{k=0}^{n}k!left{{n+1}atop{k+1} ight}left({z over {1-z}} ight)^{k+1}\ { m Li}_{-n}(z)={1 over (1-z)^{n+1}}sum _{k=0}^{n-1}leftlangle {n atop k} ight angle z^{n-k}$