基础数论

快速幂：

用来快速求m的n次幂，并取模

矩阵乘法：

当且仅当前一个矩阵的列数等于第二个矩阵的行数时，可以进行矩阵乘法，矩阵乘法不满***换律，满足结合律.\[C_{ij}=\sum\limits_{k=1}^n{A_{ik}*B_{kj}}\]

方阵可以进行矩阵快速幂。单位矩阵的对角线上都是1，单位矩阵乘任何矩阵都会得到原矩阵。矩阵快速幂可以优化递推式（比如斐波那切数列）

扩展欧几里得(exgcd)

给定a和b求解\(ax+by=gcd(a,b)\)

\[a1=b,b1=amodb\]根据欧几里得，gcd(a,b)=gcd(a1,b1）,所以\(ax+by=a1x+b1y\)即\(bx+amodb*y=ax+by\),a%b=a-b*(a/b),所以\[ax+by=bx+(a-b*(a/b))*y\]\[ax+by=bx+ay-b*(a/b)*y\]\[ax+by=ay+b(x-(a/b)y)\]\[所以，x=y,y=x-(a/b)*y\]

然后在欧几里得的基础上不断按照上面的结论递归求解即可

int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int tmp=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return tmp;
}

线性筛素数

for(int i=2;i<=n;++i)
{
    if(!vis[i]) dis[++js]=1;
    for(int j=1;j<=js&&dis[j]*i<=n;++j)
    {
        vis[dis[j]*i]=1;
        if(i%dis[j]==0) break;
    }
}

证明：

(1)每个合数都会被筛掉：\[设合数c=p_1*p_2*p_3···*p_i\]在枚举到c之前，\(p_2*p_3*p_4···*p_i\)肯定已经被枚举过了，然后枚举所有已经找到的质数的时候，p₁肯定也肯定会被枚举到，所以c一定会被\(p_1*p_2*p_3···*p_i\)筛掉

(2)每个合数只会被筛一次：

在循环中if(i%dis[j]==0) break;保证了每个合数只会被它最小的质因子p₁筛掉，然后就能保证每个合数只会被他最小的质因子筛掉一次

欧拉函数

性质:

(1) φ(n)=n-1 n是质数

(2)φ(n) < n-1 n是合数

(3)φ(i)φ(j)=φ(ij) 当gcd(i,j)互质时

线性筛欧拉函数

void Phi() {
    int js = 0;
    phi[1] = 1;
    for(int i = 2;i <= N;++i) {
        if(!vis[i]) dis[++js] = i,phi[i] = i - 1;
        for(int j = 1;j <= js && dis[j] * i <= N;++j) {
            vis[i * dis[j]] = 1;
            if(i % dis[j] == 0) {
                phi[i * dis[j]] = phi[i] * dis[j];
                break;
            }
            phi[i * dis[j]] = phi[i] * (dis[j] - 1);
        }
    }
    return;
}

逆元

对于单个逆元

根据\(x^{φ(p)}≡1 (mod p)\)在gcd(x,p)=1的情况下,可以得出\(x*x^{φ(p)-1}≡1(mod p)\) 可以直接算出\(x^{φ(p)-1}\)得出结果。但是算φ(p)是sqrt(p)的复杂度，但是当p是质数的时候φ(p)=p-1，可以直接用快速幂算出答案。

如果p不是质数，可以用exgcd求解。因为\(x*x^{-1}≡1(mod p)\)所以\(x*x^{-1}+p*y≡1\)然后用exgcd求解即可

对于一个范围内的逆元

递推线性求解，具体证明与代码

组合数取模

杨辉三角：

根据二项式定理：\[(a+b)^n=C_n^0a^n+C_n^1a^{n-1}b+C_n^2a^{n-1}b^2……+C_n^nb^n\]其中\(C_n^m\)为系数，然后系数又满足杨辉三角。所以可以利用线性求杨辉三角第n行的方法求解。

关于杨辉三角第n行的求法，其实还是利用组合数推出的。我们知道\[C_n^i=\frac{n!}{i!(n-i)!}\qquad C_n^{i+1}=\frac{n!}{(i+1)!(n-i-1)!}\]

\[=\frac{n!(i+1)}{(i+1)!(n-i)!}\ \qquad =\frac{n!(n-i)}{(i+1)!(n-i)!}\]

然后就可以推出\(C_n^{i+1}=C_n^i/(i+1)*(n-i)\)为了保证精度，所以\(C_n^{i+1}=C_n^i*(n-i)/(i+1)\)然后发现这里面有除法，所以要预处理出1到n的逆元然后这种方法递推即可，复杂度O(n)

但是经过一晚上的测试发现这种方法不可行!!!!因为中间会有某个组合数变成0，而整个递推的过程都是乘法，之后的组合数就全部推成0了，，凉凉。但是可以用来求不取模的情况下第n行的杨辉三角。或者是n小于一千的组合数

卢卡斯定理（不会证明gg）

定理：\[C_n^i\%p=C_{n/p}^{i/p}*C_{n\%p}^{i\%p}\%p\]

利用卢卡斯定理，可以将\(C_n^m\)转化成n小于p的组合数进行求解。\(C_n^m=\frac{n!}{m!(n-m)!}\)所以要预处理出m!和(n-m)!的逆元，然后求即可

code

#include<cstdio>
#include<iostream>
using namespace std;
const int N=100000*2;
typedef long long ll;
int T,p,n,m;
ll a[N],b[N];
ll C(int x,int y)
{
    if(x>y) return 0;
    if(y<p) return b[y]*a[x]%p*a[y-x]%p;
    return C(x/p,y/p)*C(x%p,y%p)%p;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&p);
        a[0]=a[1]=b[1]=b[0]=1;
        for(int i=2;i<=m+n;++i)
            b[i]=b[i-1]*i%p;
        for(int i=2;i<=m+n;++i)
            a[i]=(p-p/i)*a[p%i]%p;
        for(int i=2;i<=m+n;++i)
            a[i]=a[i-1]*a[i]%p;
        cout<<C(m,m+n)<<endl;;

    }
    return 0;
}