1228 序列求和 (伯努利数)

简介: 1228 序列求和 (伯努利数)

1228 序列求和

3 秒 131,072 KB 160 分 6 级题

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的结果即可。

输入

第1行:一个数T,表示后面用作输入测试的数的数量。(1 <= T <= 5000)

第2 - T + 1行:每行2个数,N, K中间用空格分割。(1 <= N <= 10^18, 1 <= K <= 2000)

输出

共T行,对应S(n) Mod 1000000007的结果。

输入样例

3

5 3

4 2

4 1

输出样例

225

30

10


求自然数的幂和,有一个基于伯努利数的公式。1.png

于是线性处理出每一项,那么每个case就是线性求解了。

伯努利数怎么计算呢?

首先B0=1,然后有

2.png

将Bn提取出来,得到3.png

这样就能递推伯努利数了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2010;
const int N = 2005;
typedef long long ll;
const ll mod = 1e9 + 7;
ll inv[maxn], b[maxn], fac[maxn];
ll fiv[maxn];
ll qpow(ll a, ll b) {
  ll ans = 1;
  while (b) {
    if (b & 1) {
      ans = (ans * a) % mod;
    }
    a = (a * a) % mod;
    b >>= 1;
  }
  return ans % mod;
}
ll C(ll n, ll m) {
  return fac[n] * fiv[m] % mod * fiv[n - m] % mod;
}
int main() {
  b[0] = 1; inv[1] = 1, fac[0] = 1,fiv[0] = 1;
  for (int i = 2; i <= N; i++) {
    inv[i] = (mod - mod / i) * inv[mod % i] % mod;
  }
  for (int i = 1; i <= N; i++) {
    fac[i] = fac[i - 1] * i % mod;
    fiv[i] = qpow(fac[i], mod - 2);
  }
  for (int i = 1; i <= N; i++) {
    ll sum = 0;
    for (int j = 0; j < i; j++) {
      sum = (sum + C(i + 1, j) * b[j]) % mod;
    }
    b[i] = -inv[i + 1] * sum;
    b[i] = (b[i] % mod + mod) % mod;
  }
  ll T, n, k;
  cin >> T;
  while (T--) {
    cin >> n >> k;
    ll p = (n + 1) % mod; ll mul = p;
    ll ans = 0;
    for (int i = 1; i <= k + 1; i++) {
      ans = (ans + C(k + 1, i) * b[k + 1 - i] % mod * mul % mod) % mod;
      mul = mul * p % mod;
    }
    cout << ans * inv[k + 1] % mod << endl;
  }
  return 0;
}
相关文章
|
3月前
|
存储 C语言 Python
有一分数序列:2/1,3/2,5/3,8/5,13/8,21/13…求出这个数列的前20项之和。
有一分数序列:2/1,3/2,5/3,8/5,13/8,21/13…求出这个数列的前20项之和。
647 4
|
4月前
|
Python
累加求和 1~ n求和
累加求和 1~ n求和
86 4
|
6月前
分数序列
【6月更文挑战第9天】分数序列。
50 5
|
7月前
16.有一分数序列 1/2,2/3,3/5,5/8,8/13,13/21,…求出这个序列的前200 项之和
16.有一分数序列 1/2,2/3,3/5,5/8,8/13,13/21,…求出这个序列的前200 项之和
76 0
|
7月前
分数1/1-1/2+1/3-1/4+1/5 …… + 1/99 - 1/100 求和
分数1/1-1/2+1/3-1/4+1/5 …… + 1/99 - 1/100 求和
94 0
wustojc3010快速求和
wustojc3010快速求和
62 0
7-234 两个有序序列的中位数
7-234 两个有序序列的中位数
115 0
|
存储
[递推]双幂序列、多幂序列、双幂积序列的和
[递推]双幂序列、多幂序列、双幂积序列的和
215 0
[递推]双幂序列、多幂序列、双幂积序列的和
|
存储 算法 索引
算法 | 100000 个数的求和只需要 O(1),可能吗?
算法 | 100000 个数的求和只需要 O(1),可能吗?
114 0
算法 | 100000 个数的求和只需要 O(1),可能吗?