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的结果即可。
拉格朗日插值：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9 + 7; const int maxn = 50000 + 10; const int N = maxn; ll fac[maxn], pl[maxn], pr[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; } int main() { fac[0] = 1; for (int i = 1; i <= N; i++) { fac[i] = fac[i - 1] * i % mod; } int T; scanf("%d", &T); while (T--) { ll n, k, y=0, ans = 0; scanf("%lld%lld", &n, &k); pl[0] = pr[k + 3] = 1; for (int i = 1; i <= k + 2; i++) { pl[i] = pl[i - 1] * (n % mod - i + mod) % mod; } for (int i = k + 2; i >= 1; i--) { pr[i] = pr[i + 1] * (n % mod - i + mod) % mod; } for (int i = 1; i <= k + 2; i++) { y = (y + qpow(i, k)) % mod; ll a = pl[i - 1] * pr[i + 1] % mod; ll b = fac[i - 1] * ((k + 2 - i) & 1 ? -1 : 1) * fac[k + 2 - i]; b = (b % mod + mod) % mod; ans = (ans + y * a % mod * qpow(b, mod - 2) % mod) % mod; } printf("%lld\n", ans); } return 0; }
