题目链接：
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1228&judgeId=550328
就是求自然数幂的和
伯努利数来求
早就听说过伯努利数了，但是感觉太难了，一直没管，但是今天因为队友的一道题，突然推出一个递推式，貌似阔以用
O
(
n
2
)
O(n^2)
O(n2)解决。。。结果别人的测试数据有几千组，每组都是
O
(
n
2
)
O(n^2)
O(n2)的话就超时了，而伯努利数的这种方法是先
O
(
n
2
)
O(n^2)
O(n2)求出伯努利数，然后再用
O
(
n
)
O(n)
O(n)求出每组测试数据，这样就不得超时了
伯努利数的递推式：
∑
i
=
0
k
C
k
+
1
i
B
i
=
0
\sum_{i=0}^{k}C_{k+1}^iB_i=0
i=0∑kCk+1iBi=0每个
B
k
B_k
Bk都用这个算一下，就是
O
(
n
2
)
了
O(n^2)了
O(n2)了
然后计算答案用这个公式：
1
k
+
1
∑
i
=
1
k
+
1
C
k
+
1
i
B
k
+
1
−
i
(
n
+
1
)
i
\frac{1}{k+1}\sum_{i=1}^{k+1}C^i_{k+1}B_{k+1-i}(n+1)^i
k+11i=1∑k+1Ck+1iBk+1−i(n+1)i
伯努利这个公式怎么来的我也不知道。。。希望有一天能够懂怎么来的
#include"bits/stdc++.h"
using namespace std;
const int maxn=2e3+5;
const long long MOD=1e9+7;
long long fac[maxn],inv[maxn];
long long N,K,T;
long long B[maxn];//伯努利数
long long ksm(long long a,long long b)
{
long long res=1,base=a;
while(b)
{
if(b&1)res=(res*base)%MOD;
base=(base*base)%MOD;
b>>=1;
}
return res;
}
void Init()
{
fac[0]=fac[1]=inv[0]=inv[1]=1;
for(long long i=2;i<=2002;i++)
{
fac[i]=(fac[i-1]*i)%MOD;
inv[i]=(inv[i-1]*ksm(i,MOD-2))%MOD;
}
}
long long C(int n,int m)
{
if(m==0||n==m)return 1;
long long res=(fac[n]*inv[m])%MOD;
res=(res*inv[n-m])%MOD;
return res;
}
void Bernoulli()//O(n^2)求伯努利数
{
B[0]=1;
long long sum=1;
for(int i=1;i<=2001;i++)
{
long long tp=0;
for(int j=0;j<i;j++)tp=(tp+C(i+1,j)*B[j])%MOD;
B[i]=((MOD-tp)*ksm(i+1,MOD-2))%MOD;
}
}
long long f()//O(n)求答案
{
long long p[maxn]={1};
for(int i=1;i<=K+1;i++)p[i]=(p[i-1]*(N+1))%MOD;
long long res=0;
for(int i=1;i<=K+1;i++)
{
long long tp=(C(K+1,i)*B[K+1-i])%MOD;
tp=(tp*p[i])%MOD;
res=(res+tp)%MOD;
}
res=(res*ksm(K+1,MOD-2))%MOD;
return res;
}
int main()
{
Init();
Bernoulli();
cin>>T;
while(T--)
{
cin>>N>>K;
N%=MOD;//开始忘了加上这句话。。。。。
cout<<f()<<endl;
}
}
递推式来求
以平方和来举例：
二
项
式
展
开
:
(
n
+
1
)
3
=
C
3
0
1
0
n
3
+
C
3
1
1
1
n
2
+
C
3
2
1
2
n
1
+
C
3
3
1
3
n
0
二项式展开:(n+1)^3=C_3^01^0n^3+C_3^11^1n^2+C_3^21^2n^1+C_3^31^3n^0
二项式展开:(n+1)3=C3010n3+C3111n2+C3212n1+C3313n0
把第一项移到左边去，并且系数是1,就省略了
(
n
+
1
)
3
−
n
3
=
C
3
1
1
1
n
2
+
C
3
2
1
2
n
1
+
C
3
3
1
3
n
0
(n+1)^3-n^3=C_3^11^1n^2+C_3^21^2n^1+C_3^31^3n^0
(n+1)3−n3=C3111n2+C3212n1+C3313n0
然后就开始推
(
n
+
1
)
3
−
n
3
=
C
3
1
1
1
n
2
+
C
3
2
1
2
n
1
+
C
3
3
1
3
n
0
(n+1)^3-n^3=C_3^11^1n^2+C_3^21^2n^1+C_3^31^3n^0
(n+1)3−n3=C3111n2+C3212n1+C3313n0
(
n
)
3
−
(
n
−
1
)
3
=
C
3
1
1
1
(
n
−
1
)
2
+
C
3
2
1
2
(
n
−
1
)
1
+
C
3
3
1
3
(
n
−
1
)
0
(n)^3-(n-1)^3=C_3^11^1(n-1)^2+C_3^21^2(n-1)^1+C_3^31^3(n-1)^0
(n)3−(n−1)3=C3111(n−1)2+C3212(n−1)1+C3313(n−1)0
(
n
−
1
)
3
−
(
n
−
2
)
3
=
C
3
1
1
1
(
n
−
2
)
2
+
C
3
2
1
2
(
n
−
2
)
1
+
C
3
3
1
3
(
n
−
2
)
0
(n-1)^3-(n-2)^3=C_3^11^1(n-2)^2+C_3^21^2(n-2)^1+C_3^31^3(n-2)^0
(n−1)3−(n−2)3=C3111(n−2)2+C3212(n−2)1+C3313(n−2)0
.
.
.
…
...
(
2
−
1
)
3
−
1
3
=
C
3
1
1
1
1
2
+
C
3
2
1
2
1
1
+
C
3
3
1
3
1
0
(2-1)^3-1^3=C_3^11^11^2+C_3^21^21^1+C_3^31^31^0
(2−1)3−13=C311112+C321211+C331310
然后把这
n
n
n个式子求和，左边一加一减一加一减就只剩下
(
n
+
1
)
3
−
1
3
(n+1)^3-1^3
(n+1)3−13，所以
(
n
+
1
)
3
−
1
3
=
C
3
1
1
1
(
1
2
+
2
2
+
.
.
.
+
n
2
)
+
C
3
2
1
2
(
1
1
+
2
1
+
.
.
.
+
n
1
)
+
C
3
3
1
3
(
1
0
+
2
0
+
.
.
.
+
n
0
)
(n+1)^3-1^3=C_3^11^1(1^2+2^2+…+n^2)+C_3^21^2(1^1+2^1+…+n^1)+C_3^31^3(1^0+2^0+…+n^0)
(n+1)3−13=C3111(12+22+...+n2)+C3212(11+21+...+n1)+C3313(10+20+...+n0)
简写一哈就是这样：
A
=
C
3
1
1
1
I
2
+
C
3
2
1
2
I
1
+
C
3
3
1
3
I
0
A=C_3^11^1I_2+C_3^21^2I_1+C_3^31^3I_0
A=C3111I2+C3212I1+C3313I0
其中:
A
=
(
n
+
1
)
3
−
1
,
只
需
要
对
数
级
别
的
快
速
幂
计
算
一
哈
就
行
A=(n+1)^3-1,只需要对数级别的快速幂计算一哈就行
A=(n+1)3−1,只需要对数级别的快速幂计算一哈就行
I
2
就
是
我
们
要
求
的
答
案
平
方
和
,
I
1
是
一
次
方
和
,
I
0
是
0
次
方
和
I_2就是我们要求的答案平方和,I_1是一次方和,I_0是0次方和
I2就是我们要求的答案平方和,I1是一次方和,I0是0次方和
所以递推一次差不多要
k
k
k次运算，然后要差不多
k
k
k次递推，所以是
k
2
k^2
k2的复杂度
/*递推版，每一计算是O(k^2),过不了*/
#include"bits/stdc++.h"
using namespace std;
const int maxn=2e3+5;
const int MOD=1e9+7;
long long dp[maxn];
long long fac[maxn],inv[maxn];
long long N,K,T;
long long C[maxn][maxn];
long long ksm(long long a,long long b)
{
long long res=1,base=a;
while(b)
{
if(b&1)res=(res*base)%MOD;
base=(base*base)%MOD;
b>>=1;
}
return res;
}
void Init()
{
fac[0]=fac[1]=inv[0]=inv[1]=1;
for(long long i=2;i<=2000;i++)
{
fac[i]=(fac[i-1]*i)%MOD;
inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
}
for(int i=0;i<=2000;i++)
{
C[i][0]=C[i][i]=1;
for(int j=1;j<i;j++)
{
C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
}
}
}
long long f(int k)
{
long long res=(ksm(N+1,k+1)-1+MOD)%MOD;
long long tp=0;
for(int i=2;i<=k+1;i++)
{
tp+=(C[k+1][i]*dp[k+1-i])%MOD;
tp%=MOD;
}
res=(res-tp+MOD)%MOD;
res=(res*ksm(k+1,MOD-2))%MOD;
return dp[k]=res;
}
int main()
{
Init();
cin>>T;
while(T--)
{
cin>>N>>K;
dp[0]=N%MOD;
for(int i=1;i<=K;i++)f(i);
cout<<dp[K]<<endl;
}
}