http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1258
基准时间限制：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 ;
}