51nod 1228 序列求和【伯努利数】【自然数幂的和】

本文主要是介绍51nod 1228 序列求和【伯努利数】【自然数幂的和】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

题目链接：
伯努利数来求
递推式来求

题目链接：

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1228&judgeId=550328
就是求自然数幂的和

伯努利数来求

早就听说过伯努利数了，但是感觉太难了，一直没管，但是今天因为队友的一道题，突然推出一个递推式，貌似阔以用 $O(n^2)$ 解决。。。结果别人的测试数据有几千组，每组都是 $O(n^2)$ 的话就超时了，而伯努利数的这种方法是先 $O(n^2)$ 求出伯努利数，然后再用 $O (n)$ 求出每组测试数据，这样就不得超时了

伯努利数的递推式： $\sum_{i=0}^{k}C_{k+1}^iB_i=0$ 每个 $B_k$ 都用这个算一下，就是 $O(n^2)了$

然后计算答案用这个公式：
$\frac{1}{k+1}\sum_{i=1}^{k+1}C^i_{k+1}B_{k+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^01^0n^3+C_3^11^1n^2+C_3^21^2n^1+C_3^31^3n^0$
把第一项移到左边去，并且系数是1,就省略了
$n+1)^3-n^3=C_3^11^1n^2+C_3^21^2n^1+C_3^31^3n^0$
然后就开始推
$n+1)^3-n^3=C_3^11^1n^2+C_3^21^2n^1+C_3^31^3n^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-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$
$. . .$
$2-1)^3-1^3=C_3^11^11^2+C_3^21^21^1+C_3^31^31^0$

然后把这 $n$ 个式子求和，左边一加一减一加一减就只剩下 $n+1)^3-1^3$ ，所以
$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)$
简写一哈就是这样：
$A=C_3^11^1I_2+C_3^21^2I_1+C_3^31^3I_0$
其中:
$A=(n+1)^3-1,只需要对数级别的快速幂计算一哈就行$
$I_2就是我们要求的答案平方和,I_1是一次方和,I_0是0次方和$
所以递推一次差不多要 $k$ 次运算，然后要差不多 $k$ 次递推，所以是 $k^2$ 的复杂度

/*递推版，每一计算是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;}
}