小議一類數列求和

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

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

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

Description

考慮求

Analysis

我們首先記它為。

特殊情形

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

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

移項整理就有

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

擾動法專題

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

大體就都是這樣的步驟。

練習題 試使用擾動法求。這題同上稍有不同，但只要注意總結和變通，也很好處理。

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

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

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

得

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

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

#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;
}

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

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

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

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

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

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

命題對於任意，存在使得

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

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

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

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

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

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

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

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

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

blog.miskcoo.com

你以為這就完了嗎？

考慮多對數函數

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

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

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

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

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

那麼能不能利用多對數函數快速求出呢？

我也不知道QAQ

但是那並不能改進複雜度呀

TAT