欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

[数论]伯努利数

程序员文章站 2022-03-28 19:09:59
线性求逆元快速版#include#define MOD mod#define MAX maxnusing namespace std;typedef pair 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...

线性求逆元快速版

#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