「OI之路」03数学-9自然数幂和

自然数幂和的几种解法,可以感受一下各种数学工具的特性,也是经典的求和问题

自然数幂和指,$\sum_{i=1}^n i^k$

板子是 51nod1258 序列求和 V4

第二类斯特林数

这个做法提供给不知道结论的选手,没有每个k回答时,都至少需要klogk预处理,然后单次回答是O(k)

$a^b=\sum_{i=1}^a S_2(b,i) \cdot i! \cdot C_a^i,\sum_{i=0}^n i^k=\sum( \sum_{j=1}^k S_2(k,j) \cdot j! \cdot C_i^j )$
因为希望和k有关,把j提出来$\sum_{j=1}^k S_2(k,j) \cdot j! \times ( \sum_{i=0}^n C_i^j )$
然后根据组合数的性质$\sum_{j=1}^k S_2(k,j) \cdot j! \times C_{n+1}^{j+1}$
类似思想:bzoj5093,比较套路

顺便提一下,如果模数不好求组合数也是能求自然数幂和的,就是写成$\sum_{j=0}^k S_2(k,j)*\frac{(n+1)^\underline{ (j+1)}}{j+1}$,找到j+1的那个倍数

拉格朗日插值

结论:对于某个k,自然数幂和可以表示为一个n为未知数的k+1次多项式

这个可以观察、归纳之类的,不过从上面那个做法中也可以直接得到印证(没想到吧

直接套插值,处理前缀积和后缀积和阶乘的逆元,然后$i^k$用线性筛求,$O(k)$

1
2
3
4
5
6
7
8
9
10
11
12
13
ll n=qread(),k=qread();
pw[1]=y[1]=1;
fo(i,2,k+1) pw[i]=(nop[i]?1ll*pw[mip[i]]*pw[i/mip[i]]%MOD:qpower(i,k)),y[i]=mm(y[i-1]+pw[i]);
if(n<=k+1){ write2(y[n]);continue; }
sufs[k+2]=1; fd(i,k+1,1) sufs[i]=(n-i)%MOD*sufs[i+1]%MOD;
pres[0]=n%MOD;fo(i,1,k+1) pres[i]=(n-i)%MOD*pres[i-1]%MOD;
int ans=0;
fo(i,1,k+1)
{
int fz=pres[i-1]*sufs[i+1]%MOD;
int fm=facinv[i]*((k+1-i)&1?MOD-1:1)%MOD*facinv[k+1-i]%MOD;
add(ans, 1ll*y[i]*fz%MOD*fm%MOD );
} write2(ans);

伯努利数的前半部分

伯努利数这玩意,对于单组$n,k$的询问,复杂度为k,和插值一样,除了一点点常数外,基本没有优势

对于固定n,同时求每个k的答案,只需要做一次$O(klogk)$的卷积,这才是其优势,但完全不需要引入伯努利数

所以伯努利数并没有啥用,介绍伯努利数时前面推的东西(虽然很短)才是有用的部分

既然n固定,考虑Sk的生成函数
$$
\begin{aligned}
如果使用OGF,S(x)&=\sum_{k=0}^{\infty}S_k(n) x^k=\sum_{k=0}^{\infty} \sum_{i=0}^n i^k x^k=\sum_{i=0}^n \frac{1}{1-ix},好像不太行
\\
换成EGF,S(x)&=\sum_{k=0}^{\infty}S_k(n)\frac{x^k}{k!} =\sum_{k=0}^{\infty}\sum_{i=0}^n i^k\frac{x^k}{k!}=\frac{e^{(n+1)x}-1}{e^x-1} \\
\end{aligned}
$$
下面多项式没有逆元不能直接计算,但上下同时除x,就没问题了

一次多项式求逆,$O(klogk)$

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/1f2a.html
转载请注明出处,谢谢!