[数论]伯努利数

线性求逆元快速版

#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