51nod 1258 序列求和 V4

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1258

1258 序列求和 V4 

基准时间限制：8 秒 空间限制：131072 KB 分值: 1280 难度：9级算法题

 收藏

 关注

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 <= 500)

第2 - T + 1行：每行2个数，N, K中间用空格分割。(1 <= N <= 10^18, 1 <= K <= 50000)

Output

共T行，对应S(n) Mod 1000000007的结果。

Input示例

3

5 3

4 2

4 1

Output示例

225

30

10

拉格朗日插值法

注意观察 插值表达式分子分母的性质，递推得每一项的值

#include<cstdio>

#include<iostream>

using namespace std;

const int mod=1e9+;

typedef long long LL;

int sum[];

int jc[],inv[];

int l[],r[];

template<typename T>

void read(T &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

int Pow(int a,int b)

{

    int res=;

    for(;b;a=1LL*a*a%mod,b>>=)

        if(b&) res=1LL*res*a%mod;

    return res;

}

int solve(LL n,int k)

{

    if(n<=k+) return sum[n];

    n%=mod;

    int w=Pow(jc[k+],mod-);

    l[]=;

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

    r[k+]=;

    for(int i=k+;i;--i) r[i]=1LL*r[i+]*(n-i)%mod;

    int ans=;

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

    {

        ans=(ans+1LL*sum[i]*w%mod*l[i-]%mod*r[i+]%mod)%mod;

        w=1LL*w*(i-k-)%mod*inv[i]%mod;

    }

    if(ans<) ans+=mod;

    return ans;

}

int main()

{

    int T;

    read(T);

    LL n; int k;

    inv[]=;

    for(int i=;i<=;++i) inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;

    jc[]=;

    for(int i=;i<=;++i) jc[i]=1LL*jc[i-]*(-i)%mod;

    while(T--)

    {

        read(n); read(k);

        for(int i=;i<=k+;++i) sum[i]=(sum[i-]+Pow(i,k))%mod;

        printf("%d\n",solve(n,k));

    }

    return ;

}