51Nod - 1228 序列求和 （自然数幂和+伯努利数）

https://vjudge.net/problem/51Nod-1228

Description

T(n) = n^k，S(n) = T(1) + T(2) + ...... T(n)。给出n和k，求S(n)。

例如k = 2，n = 5，S(n) = 1^2 + 2^2 + 3^2 + 4^2 + 5^2 = 55。

由于结果很大，输出S(n) Mod 1000000007的结果即可。

Input

第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 5000)

第2 - T + 1行：每行2个数，N, K中间用空格分割。(1 <= N <= 10^18, 1 <= K <= 2000)Output共T行，对应S(n) Mod 1000000007的结果。

Sample Input

3

5 3

4 2

4 1

Sample Output

225

30

10

分析

求自然数的幂和，有一个基于伯努利数的公式。

于是线性处理出每一项，那么每个case就是线性求解了。

伯努利数怎么计算呢？

首先B0=1，然后有

将Bn提取出来，得到

这样就能递推伯努利数了。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <string>

#include <algorithm>

#include <cmath>

#include <ctime>

#include <vector>

#include <queue>

#include <map>

#include <stack>

#include <set>

#include <bitset>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

#define ms(a, b) memset(a, b, sizeof(a))

#define pb push_back

#define mp make_pair

#define pii pair<int, int>

#define eps 0.0000000001

#define IOS ios::sync_with_stdio(0);cin.tie(0);

#define random(a, b) rand()*rand()%(b-a+1)+a

#define pi acos(-1)

const ll INF = 0x3f3f3f3f3f3f3f3fll;

const int inf = 0x3f3f3f3f;

const int maxn =  + ;

const int maxm =  + ;

const int mod = 1e9+;

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

inline ll add(ll a){

    if(a>=mod) a-=mod;

    return a;

}

void init(){

    C[][]=;

    for(int i=;i<maxn;i++){

        C[i][]=C[i][i]=;

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

            C[i][j]=add(C[i-][j-]+C[i-][j]);

        }

    }

    inv[]=;

    for(int i=;i<maxn;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod; //线性递推逆元

    B[]=;

    for(int i=;i<maxn-;i++){

        B[i]=;

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

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

        }

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

    }

}

ll tmp[maxn];

int main() {

#ifdef LOCAL

    freopen("in.txt", "r", stdin);

//    freopen("output.txt", "w", stdout);

#endif

    init();

    int T;

    scanf("%d",&T);

    while(T--){

        ll n,k;

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

        n%=mod; //这里取个模比较好，求tmp时才不会爆

        tmp[]=;

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

        ll ans=;

        for(ll i=;i<=k+;i++){

            ans=add(ans+C[k+][i]*B[k+-i]%mod*tmp[i]%mod);

        }

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

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

    }

    return ;

}