逆元 组合A(n,m) C(n,m)递推 隔板法
求逆元 https://blog.****.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; } }
组合递推
对于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; }
需要取模的组合数 预处理出所有
直接调用 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; }