SRM397 div1 medium
k乗和の公式を使う。
求め方は数学Bの教科書に載っている。
#include <algorithm> #include <string> #include <vector> #include <iostream> #include <sstream> #include <cstdio> #include <cstring> #include <cmath> #include <set> #include <map> #include <climits> using namespace std; typedef long long LL; static const LL MOD=1000000007; LL ADD(LL x,LL y){ return (x+y)%MOD; } LL SUB(LL x,LL y){ return (x-y+MOD)%MOD; } LL MUL(LL x,LL y){ return ((x*y)%MOD+MOD)%MOD; } LL POW(LL x,LL e) { LL r=1; for(;e;x=MUL(x,x),e>>=1) if(e&1) r=MUL(r,x); return r; } LL DIV(LL x,LL y){ return MUL(x,POW(y,MOD-2)); } LL COMB(LL n,LL k) { LL r=1; for(LL i=1;i<=k;i++) r=DIV(MUL(r,n-i+1),i); return r; } class SumOfPowers { public: LL n,k; LL bin[60][60]; LL cache[60]; LL rec(int p) { LL &r=cache[p]; if(r!=-1) ; else if(p==0) r=n; else if(p==1) r=n*(n+1)/2%MOD; else { r=(POW(n+1,p+1)-1)%MOD; for(int i=0;i<p;i++) { r-=MUL(bin[p+1][i],rec(i)); r=(r%MOD+MOD)%MOD; } r=DIV(r,bin[p+1][p]); } return r; } int value(int _n, int _k) { n=_n,k=_k; for(int i=0;i<60;i++) for(int j=0;j<60;j++) if(i<j) bin[i][j]=0; else if(j==0) bin[i][j]=1; else bin[i][j]=(bin[i-1][j]+bin[i-1][j-1])%MOD; /*for(int i=1;i<10;i++) for(int j=1;j<=i;j++) printf("bin[%d][%d]=%lld\n",i,j,bin[i][j]);*/ memset(cache,-1,sizeof(cache)); return rec(k); } };