逆元组合A(n,m) C(n,m)递推隔板法

求逆元 https://blog.csdn.net/baidu_35643793/article/details/75268911

int inv[N];

void init(){
    inv[1] = 1;
    for (int i = 2; i < N; ++ i){
        inv[i] = (mod - 1ll * (mod / i) * inv[mod % i] % mod) % mod;
    }
}

组合递推

牛客暑期集训第六场C题解

对于A，M个取i个排列，如果我们要使A(M,i)->A(M,i+1)只需要A(M,i) * (M-i)

对于C，N个取i个组合，如果我们要使C(N-1,i-1)->C(N-1,i)只需要

　　　　C(N-1,i-1) * (N-i)/i = C(N-1,i-1) * (N-i)*inv[i]%mod

#include <bits/stdc++.h>
#define MOD 998244353
#define MAXN 1000005
#define ll long long
using namespace std;

int NY[MAXN];
void init() {
    NY[1]=1;
    for(int i=2;i<MAXN;i++)
        NY[i]=(MOD-1ll*(MOD/i)*NY[MOD%i]%MOD)%MOD;
}

int main()
{
    init();
    int t; scanf("%d",&t);
    for(int o=1;o<=t;o++) {
        ll n,m; scanf("%lld%lld",&n,&m);
        ll A=m%MOD, C=1;
        ll ans=1ll*A%MOD;
        for(ll i=1;i<min(n,m);i++) {
            A=1ll*(m-i)%MOD*A%MOD;
            C=1ll*(n-i)%MOD*C%MOD*NY[i]%MOD;// C*((n-1)-(i-1))*NY[i]
            ans=(ans+A*C%MOD)%MOD;
        }
        printf("Case #%d: %lld
",o,ans);
    }

    return 0;
}

View Code

需要取模的组合数预处理出所有

直接调用 C(a,b) 即可

#define mod 1000000007
#define LL long long
const int N=2e5+5;
LL pow_mod(LL a, LL b) {
    LL res = 1LL; a %= mod;
    while(b){
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    } return res;
}
LL inv(LL a) { return pow_mod(a, mod-2); }
LL F[N], Finv[N];//F是阶乘，Finv是逆元的阶乘
void init() {
    F[0] = Finv[0] = 1LL;
    for(int i = 1; i < N; i ++){
        F[i] = F[i-1] * 1LL * (LL)i % mod;
        Finv[i] = Finv[i-1] * 1LL * inv(i) % mod;
    }
}
LL C(LL n, LL m) {  
    if(m < 0 || m > n) return 0;
    return F[n] * 1LL * Finv[n - m] % mod * Finv[m] % mod;
}