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

求自然数的幂和，有一个基于伯努利数的公式。

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

伯努利数怎么计算呢？

首先B0=1，然后有

将Bn提取出来，得到

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

#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;
}