快速幂

int power(int a,int b,int mod){
    int ans=1;
    while(b){
        if(1&b) ans=(ans*a)%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return ans;
}

逆元

x在模mod意义下的逆元

int inv=power(x,mod-2)%mod;

连续数字的逆元线性递推

1...n模p的逆元
inv[1]=1;
for(int i=2;i<=n;i++){
    inv[i]=(p-1ll*inv[p%i]*(p/i)%p);
}

连续数字的阶乘逆元线性递推

#求0...n的阶乘模mod的结果
fac[0]=0;
for(int i=1;i<=n;i++){
    fac[i]=(i*fac[i-1])%mod;
}
#求0...n模mod的逆元
inv[n]=power(fac[n],mod-2,mod)
for(int i=n-1;i>=0;i--){
    inv[i]=((i+1)*inv[i+1])%mod;
}

除法同余

计算a/b然后%mod的结果
前提:
1.a/b可以整除
2.mod是质数
3.b与mod互质

int inv=power(x,mod-2)%mod;
(a/b)%mod=(a%mod*inv)%mod

预处理逆元求组合数

int ans=fac[n];
ans=1ll*(ans*inv[m])%mod;
ans=1ll*(ans*inv[n-m])%mod

扩展欧几里得算法

// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a/b) * x;
    return d;
}

扩展欧几里得算法 求逆元

求a在模b下的逆元--> ax%b=1 --> ax=1+by -->ax+by=1
利用exgcd(a,b,x,y) ,求得x即为a在模b下的逆元

中国剩余定理

解同余方程 m1,m2,...,mn两两互质
* x=r1(mod m1)
* x=r2(mod m2)
* . . . . .
* x=rn(mod mn)

ll CRT(){
    ll M=1;
    for(int i=0;i<n;i++){
        cin>>m[i]>>r[i];
        M*=m[i];
    }
    ll x,y,mi,ans=0;
    for(int i=0;i<n;i++){
        mi=M/m[i];
        exgcd(mi,m[i],x,y);
        ans=(ans+(lll)mi*x*r[i]%M)%M;

    }

    return (ans%M+M)%M;
}

//解 x=k*M+tail

递推求组合数:

c[a][b]从a个球中选b个

    for(int i=0;i<N;i++){
        for(int j=0;j<=i;j++){
            if(!j) c[i][j]=1;
            else c[i][j]=c[i-1][j]+c[i-1][j-1];
        }
    }

插板法:

1.现有 n 个 完全相同 的元素，要求将其分为 k 组，保证每组至少有一个元素
c[k-1][n-1]
2.现有 n 个 完全相同 的元素，要求将其分为 k 组，无需保证每组至少有一个元素
c[k+n-1][n-1]