线性求逆元快速版
我要评论#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;
}
本文地址：https://blog.csdn.net/wulalalawu/article/details/107126446
如对本文有疑问， 点击进行留言回复！！
网友评论