线性求逆元快速版
#include<bits/stdc++.h> #define MOD mod #define MAX maxn using namespace std; typedef pair<int, int> pii; typedef long long ll; const double eps = 1e-6; const int maxn = 2e3 + 10, inf = 0x3f3f3f3f, mod = 1e9 + 7; ll quickpow(ll x, ll k) { ll res = 1; while (k){ if (k & 1) res = res * x % mod; x = x * x % mod; k >>= 1; } return res; } int B[MAX],jc[MAX],jv[MAX],inv[MAX]; int C(int n,int m){return 1ll*jc[n]*jv[m]%MOD*jv[n-m]%MOD;} void bernoulli() { B[0]=jc[0]=jv[0]=inv[0]=inv[1]=1; for(int i=2;i<MAX;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD; for(int i=1;i<MAX;++i)jc[i]=1ll*jc[i-1]*i%MOD; for(int i=1;i<MAX;++i)jv[i]=1ll*jv[i-1]*inv[i]%MOD; for(int i=1;i<MAX;++i){ for(int j=0;j<i;++j)B[i]=(B[i]+1ll*B[j]*C(i+1,j))%MOD; B[i]=1ll*B[i]*inv[i+1]%MOD;B[i]=(MOD-B[i])%MOD; } } int main() { ios::sync_with_stdio(0); cin.tie(0); bernoulli(); int t; cin >> t; while (t--){ ll n, sum = 0; int k; cin >> n >> k; n = (n + 1) % mod; for (int i = 0; i <= k; ++i){ sum += (ll)C(k + 1, i) * B[i] % mod * quickpow(n, k + 1 - i) % mod; sum %= mod; } cout << sum * quickpow(k + 1, mod - 2) % mod << '\n'; } return 0; }我的
#include<bits/stdc++.h> using namespace std; typedef pair<int, int> pii; typedef long long ll; const int maxn = 2e3 + 10, inf = 0x3f3f3f3f, mod = 1e9 + 7; ll quickpow(ll x, ll k) { ll res = 1; while (k){ if (k & 1) res = res * x % mod; x = x * x % mod; k >>= 1; } return res; } int fac[maxn], B[maxn];; ll C(int n, int m){return (fac[n] * quickpow(((ll)fac[m] * fac[n - m]) % mod, mod - 2)) % mod;} void bernoulli()//伯努利数 { B[0] = 1; for(int i = 1; i < maxn; ++i){ for(int j = 0; j < i; ++j) B[i] = (B[i] + (ll)B[j] * C(i + 1, j) % mod) % mod; B[i] = B[i] * quickpow(i + 1, mod - 2) % mod; B[i] = (mod - B[i]) % mod; } } int main() { ios::sync_with_stdio(0); cin.tie(0); fac[0] = 1; for (int i = 1;i < maxn; ++i) fac[i] = (ll)i * fac[i - 1] % mod; bernoulli(); int t; cin >> t; while (t--){ ll n, sum = 0; int k; cin >> n >> k; n = (n + 1) % mod; ll na = n; for (int i = k; i >= 0; --i){ sum += (ll)C(k + 1, i) * B[i] % mod * na % mod; sum %= mod; na = (na * n) % mod; } cout << sum * quickpow(k + 1, mod - 2) % mod << endl; } return 0; }