51Node1228序列求和 ——自然数幂和模板&&伯努利数

伯努利数法

伯努利数原本就是处理等幂和的问题，可以推出

$$ \sum_{i=1}^{n}i^k={1\over{k+1}}\sum_{i=1}^{k+1}C_{k+1}^i*B_{k+1-i}*(n+1)^i $$

因为

$$\sum_{k=0}^nC_{n+1}^kB_k=0(B_0=1)$$

所以

$$ B_n={- {1\over{n+1}}}(C_{n+1}^0B_0+C_{n+1}^1B_1+……C_{n+1}^{n-1}B_{n-1})$$

伯努利数的证明十分复杂，记住即可。

题目

求 $\sum_{i=1}^ni^k \ mod \ (1e9+7)$，$i \leq 10^{18}, k \leq 2000, T \leq 2000$.

分析

直接用上面的公式，预处理伯努利数，时间为为 $O(k^2)$。

有 $O(klogk)$ 的方法求伯努利数，但是比较复杂，以后再学吧。

单次的时间只有 $O(k)$，$T$ 组查询不会超时。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + ;

const int maxk =  + ;

ll n, k;

ll C[maxk][maxk], inv[maxk], B[maxk];

void init()

{

    //预处理组合数

    C[][] = ;

    for(int i = ;i < maxk;i++)

    {

        C[i][] = ;

        for(int j = ;j <= i;j++)

            C[i][j] = (C[i-][j-] + C[i-][j]) % mod;

    }

    //预处理逆元

    inv[] = ;

    for(int i = ;i < maxk;i++)

        inv[i] = (mod - mod/i) * inv[mod%i] % mod;

    //预处理伯努利数

    B[] = ;

    for(int i = ;i < maxk-;i++)

    {

        ll tmp = ;

        for(int j = ;j < i;j++)

            tmp = (tmp + C[i+][j]*B[j]%mod) % mod;

        tmp = tmp * (-inv[i+]) % mod;

        B[i] = (tmp + mod) % mod;

    }

}

ll pw[maxk];

ll cal()

{

    n %= mod;　　　　//想一想为什么可以这样做

    pw[] = ;

    for(int i = ;i <= k+;i++) pw[i] = pw[i-] * (n+) % mod;

    ll ret = ;

    for(int i = ;i <= k+;i++)

        ret = (ret + C[k+][i]*B[k+-i]%mod*pw[i]%mod) % mod;

    ret = ret * inv[k+] % mod;

    return ret;

}

int main()

{

    init();

    int T;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%lld%lld", &n, &k);

        printf("%lld\n", cal());

    }

    return ;

}

参考链接：https://blog.csdn.net/acdreamers/article/details/38929067