扰动三连:

等比数列求和:

Sn=∑i=1naqi−1S_n=\sum_{i=1}^naq^{i-1}
给他日上个n+1n+1
Sn+aqn+1−1S_n+aq^{n+1-1}
=∑i=1n+1aqi−1=\sum_{i=1}^{n+1}aq^{i-1}
=a+∑i=1naqi=a+\sum_{i=1}^naq^i
=a+qSn=a+qS_n
可得

Sn=a(1−qn)1−qS_n=\frac{a(1-q^n)}{1-q}

自然数幂求和:

Snm=∑i=1nimS_n^m=\sum_{i=1}^ni^m
给他日上个n+1n+1
Snm+(n+1)mS_n^m+(n+1)^m
=∑i=1n+1im=\sum_{i=1}^{n+1}i^m
=1+∑i=1n(i+1)m=1+\sum_{i=1}^n(i+1)^m
=1+∑i=1n∑j=0mCmjij=1+\sum_{i=1}^n\sum_{j=0}^mC_m^ji^j
=1+∑j=0mCmj∑i=1nij=1+\sum_{j=0}^mC_m^j\sum_{i=1}^ni^j
=1+∑j=0m−1CmjSnj+Snm=1+\sum_{j=0}^{m-1}C_m^jS_n^j+S_n^m
自己把自己日掉了2333,不慌,发现m−1m-1那一项没有被日掉,考虑把mm换成m+1m+1
Snm+1+(n+1)m+1S_n^{m+1}+(n+1)^{m+1}
=...=...
=1+∑j=0m−1Cm+1jSnj+(m+1)Snm+Snm+1=1+\sum_{j=0}^{m-1}C_{m+1}^jS_n^j+(m+1)S_n^m+S_n^{m+1}
可得

Snm=(n+1)m+1−∑j=0m−1Cm+1jSnj−1m+1S_n^m=\frac{(n+1)^{m+1}-\sum_{j=0}^{m-1}C_{m+1}^jS_n^j-1}{m+1}

可以分治FFT一波做到mlog⁡2mm\log^2m(这里打问号)
当然可以直接拉格朗日插值做到线性。

BZOJ3157国王奇遇记:

m>1m>1
Snm=∑i=1nimmiS_n^m=\sum_{i=1}^ni^mm^i
给他日上个n+1n+1
Snm+(n+1)mmn+1S_n^m+(n+1)^mm^{n+1}
=∑i=1n+1immi=\sum_{i=1}^{n+1}i^mm^i
=m+∑i=1n(i+1)mmi+1=m+\sum_{i=1}^n(i+1)^mm^{i+1}
=m+m∑i=1n∑j=0mCmjijmi=m+m\sum_{i=1}^n\sum_{j=0}^mC_m^ji^jm^i
=m+m∑j=0mCmj∑i=1nijmi=m+m\sum_{j=0}^mC_m^j\sum_{i=1}^ni^jm^i
咦,形式好像不太一样,观察一下之后选择更改状态定义。
Snk=∑i=1nikmiS_n^k=\sum_{i=1}^ni^km^i
Snk+(n+1)kmn+1S_n^k+(n+1)^km^{n+1}
=...=...
=m+m∑j=0kCkj∑i=1nijmi=m+m\sum_{j=0}^kC_k^j\sum_{i=1}^ni^jm^i
=m+m∑j=0k−1CkjSnj+mSnk=m+m\sum_{j=0}^{k-1}C_k^jS_n^j+mS_n^k
可得

Snk=(n+1)kmn+1−m−m∑j=0k−1CkjSnjm−1S_n^k=\frac{(n+1)^km^{n+1}-m-m\sum_{j=0}^{k-1}C_k^jS_n^j}{m-1}

可以分治FFT一波做到mlog⁡2mm\log^2m(这里打问号)
这题其实也可以拉格朗日插值做到线性,更神仙的推导见51nod1822,咕咕咕

我来补了。其实这个也没什么玄妙的。
有这么一个求和的式子：

∑i=0nf(i)qi\sum_{i=0}^nf(i)q^i

其中 f(i)f(i) 是一个 kk 次多项式，那么我们可以做到 O(k)O(k) 计算。（多项式最好可以快速计算，比如单项式就可以快速计算）

主要的想法是观察发现这玩意长得很像等差乘等比的求和，只不过等差是 11 次多项式。那么我们再次尝试这个等差乘等比的做法。
设 Sn=∑i=0nf(i)qiS_n=\sum_{i=0}^nf(i)q^i

qSn=∑i=0nf(i)qi+1qS_n=\sum_{i=0}^nf(i)q^{i+1}

(1−q)Sn=f(0)q+∑i=1n(f(i)−f(i−1))qi−f(n+1)qn(1-q)S_n=f(0)q+\sum_{i=1}^n(f(i)-f(i-1))q^i-f(n+1)q^n

因为 f(i)−f(i−1)f(i)-f(i-1) 是一个 k−1k-1 次多项式，中间那个求和相当于一个子问题，只不过k--了。那么我们使用归纳法，可以假设那个求和是一个 g′(n)qn−g′(0)g'(n)q^n-g'(0)，其中 g′(n)g'(n) 是一个 k−1k-1 次多项式。这样因为 f(n+1)f(n+1) 是一个 kk 次多项式，其他的都是常数，所以可以得到 Sn=g(n)qn−g(0)S_n=g(n)q^n-g(0)，其中 g(n)g(n) 是一个 kk 次多项式。

这样我们得到这个和式的一个优美的式子，关键就是如何求这个多项式 gg。
我们有 Sn−Sn−1=g(n)qn−g(n−1)qn−1=f(n)qnS_n-S_{n-1}=g(n)q^n-g(n-1)q^{n-1}=f(n)q^n，于是 g(n)=g(n−1)q+f(n)g(n)=\frac{g(n-1)}{q}+f(n)
这样我们设 g(0)=xg(0)=x，那么由递推式可得其他的值都可以写成关于 xx 的一次函数。那么只要求出 g(0)g(0)，其他值也就得到了，就可以拉格朗日插值。
怎么求 g(0)g(0)？因为 kk 次多项式的 k+1k+1 阶差分为 00，所以可以列出方程

∑i=0k+1(−1)i(k+1i)g(k+1−i)=0\sum_{i=0}^{k+1}(-1)^i{k+1\choose i}g(k+1-i)=0

然后把 xx 代入即可解出 xx。