http://www.elijahqi.win/archives/3269 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 首先k^2的做法可以考虑用二项式定理展开 然后递归做即可 伯努利数公式 B[0]=1 B [ 0 ] = 1 ∑k=0nCkn+1×B[k]=0 ∑ k = 0 n C n + 1 k × B [ k ] = 0 考虑如何用伯努利数算自然数幂和 有公式 ∑i=1nik=1k+1∑i=1k+1Cik+1×B[k+1−i]×(n+1)i ∑ i = 1 n i k = 1 k + 1 ∑ i = 1 k + 1 C k + 1 i × B [ k + 1 − i ] × ( n + 1 ) i 预处理之后可以o(k) 解决
#include<cstdio> #include<cctype> #include<algorithm> #define ll long long using namespace std; inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++; } inline ll read(){ ll x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f; } const int mod=1000000007; const int N=2200; inline int inc(int x,int v){return x+v>=mod?x+v-mod:x+v;} int T,inv[N],c[N][N],k,b[N];ll n; int main(){ freopen("1228.in","r",stdin); T=read();inv[1]=1;int sum=0; for (int i=2;i<=2001;++i) inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod; for (int i=0;i<=2001;++i) c[i][0]=1;b[0]=1; for (int i=1;i<=2001;++i) for (int j=1;j<=i;++j) c[i][j]=inc(c[i-1][j],c[i-1][j-1]); for (int i=1;i<=2000;++i){sum=0; for (int j=0;j<i;++j) sum=inc(sum,(ll)c[i+1][j]*b[j]%mod); b[i]=(ll)-inv[i+1]*sum%mod;b[i]=(b[i]+mod)%mod; } while(T--){ n=read();k=read();int mul1=(n+1)%mod;ll mul=mul1;ll ans=0; for (int i=1;i<=k+1;++i){ ans=inc(ans,(ll)c[k+1][i]*b[k+1-i]%mod*mul%mod);mul=mul*mul1%mod; }ans=inv[k+1]*ans%mod;printf("%lld\n",ans); } return 0; }