伯努利求幂和模版

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

第二伯努利数$\sum_{i=1}^n{i^k}=\frac{{(n+B^+)}^{k+1}-(B^+)^{k+1}}{k+1}$
第一伯努利数$\sum_{i=1}^n{i^k}=\frac{1}{k+1}\sum_{i=0}^{k}{(-1)^i \binom{k+1}{i}}B_i^-n^{k+1-i}$
这里模版求的是$B^-$
模版借鉴 acdreamers 的博客
代码如下：

const ll mod = 1e9+7;
const int N = 1010;ll C[N][N];
ll B[N],Inv[N];
ll Tmp[N];
ll n;
ll pre[N];void Init()
{//预处理组合数for(int i=0; i<N; i++){C[i][0] = C[i][i] = 1;if(i == 0) continue;for(int j=1; j<i; j++)C[i][j] = (C[i-1][j] % mod + C[i-1][j-1] % mod) % mod;}//预处理逆元Inv[1] = 1;for(int i=2; i<N; i++)Inv[i] = (mod - mod / i) * Inv[mod % i] % mod;//预处理伯努利数B[0] = 1;for(int i=1; i<N; i++){ll ans = 0;if(i == N - 1) break;for(int j=0; j<i; j++){ans += C[i+1][j] * B[j];ans %= mod;}ans *= -Inv[i+1];ans = (ans % mod + mod) % mod;B[i] = ans;}
}ll Work(int k)  //求k次幂的和
{ll ans = Inv[k+1];ll sum = 0;for(int i=0; i<=k; i++){if(i&1)sum=(sum-C[k+1][i] * Tmp[k+1-i] % mod * B[i] % mod+mod)%mod;elsesum += C[k+1][i] * Tmp[k+1-i] % mod * B[i] % mod;sum %= mod;}ans *= sum;ans %= mod;return ans;
}

这篇关于伯努利求幂和模版的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---