一、![\LARGE {\color{Red} a^{b}\, \, mod\, \, p}](https://private.codecogs.com/gif.latex?%5CLARGE%20%7B%5Ccolor%7BRed%7D%20a%5E%7Bb%7D%5C%2C%20%5C%2C%20mod%5C%2C%20%5C%2C%20p%7D)
ll qpow(ll a,ll b,ll p)
{
ll ret=1;a%=p;
while(b)
{
if(b&1) ret=ret*a%p;
b/=2;a=a*a%p;
}
return ret;
}
二、Lucas
ll lucas(ll n,ll m,ll p)
{
if(m==0) return 1;
return C(n%p,m%p,p)*lucas(n/p,m/p,p)%p;
}
三、C(n,m)
方案一:(直接算)
ll C(ll n,ll m,ll p)
{
if(m>n) return 0;
ll ans=1;
for(int i=1;i<=m;i++)
{
ll a=(n+i-m)%p;
ll b=i%p;
ans=ans*(a*qpow(b,p-2,p)%p)%p;
}
return ans;
}
方案二:(预处理)
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=b;i>=a;i--)
using namespace std;
#define ll long long
const int N=2010;
const int mod = 998244353;
int fac[N+10],inv[N+10];
ll rd()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int sum(int a, int b) {
int s = (a + b);
if (s >= mod) s -= mod;
return s;
}
int sub(int a, int b) {
int s = a - b;
if (s < 0) s += mod;
return s;
}
int mult(int a, int b) {
return (1LL * a * b) % mod;
}
ll qpow(ll a,ll b)
{
ll ret=1;a%=mod;
while(b)
{
if(b&1) ret=ret*a%mod;
b/=2;a=a*a%mod;
}
return ret;
}
int C(int m,int n)
{
if(m>n) return 0;
return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main()
{
fac[0]=inv[0]=1;
rep(i,1,N) fac[i]=mult(fac[i-1],i);
inv[N]=qpow(fac[N],mod-2);
dep(i,1,N-1) inv[i]=mult(inv[i+1],i+1);
}
ll C(ll n,ll m)
{
if(m>n) return 0;
return 1ll * fac[n] * inv[m] % p * inv[n - m] % p;
}
fac[0]=1;inv[0]=1;
for(int i=1;i<=p;i++)
{
fac[i]=1ll*fac[i-1]*i%p;
inv[i]=qpow(fac[i],p-2);
}
fac[0]=inv[0]=1;
rep(i,1,100) fac[i]=mult(fac[i-1],i);
inv[100]=qpow(fac[100],mod-2);
dep(i,1,99) inv[i]=mult(inv[i+1],i+1);
方案三:(预处理质数)
void isprime()
{
for(int i=2;i<=N;i++)
{
if(!flag[i]) prime[++l]=i;
num[i]=l;
for(int j=1;j<=l;j++)
{
if(1ll*prime[j]*i>N) break;
flag[prime[j]*i]=1;
if(i%prime[j]==0) break;
}
}
}
void init()
{
for(int i=1;i<=l;i++)
{
//printf("%d\n",i);
f[i][0]=inv[i][0]=1;
for(int j=1;j<prime[i];j++)
{
f[i][j]=(f[i][j-1]*j)%prime[i];
inv[i][j]=qpow(f[i][j],prime[i]-2,prime[i]);
}
}
}
ll C(ll n,ll m,ll p)
{
if(m>n) return 0;
if(m==n) return 1;
int t=num[p];//第几个质数
return f[t][n]*(inv[t][n-m]*inv[t][m]%p)%p;
}
四、组合数+中国剩余定理
ll gcd(ll a,ll b)
{
return b==0?a:gcd(b,a%b);
}
void exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0){x=1;y=0;return;}
exgcd(b,a%b,x,y);
ll t=x;
x=y;y=t-a/b*y;
}
ll work(int n)
{
ll x,y,a,b,c,t,U=u[1],V=v[1];
rep(i,2,n)
{
a=U;b=u[i];c=v[i]-V;
t=gcd(a,b);
if(c%t!=0) return -1;
a/=t;b/=t;c/=t;
exgcd(a,b,x,y);
x=((c*x)%b+b)%b;
if(!x) x+=b;
V=U*x+V,U=a*b*t,V%=U;
}
return (V%U+U)%U;
}
ll qpow(ll a,ll b,ll p)
{
ll ans=1;
a%=p;
while(b)
{
if(b&1) {ans=ans*a%p;b--;}
b>>=1;a=a*a%p;
}
return ans;
}
ll C(ll n,ll m,ll p)
{
if(m>n) return 0;
ll ans=1;
for(int i=1;i<=m;i++)
{
ll a=(n+i-m)%p;
ll b=i%p;
ans=ans*(a*qpow(b,p-2,p)%p)%p;
}
return ans;
}
ll Lucas(ll n,ll m,ll p)
{
if(m==0) return 1;
return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
}