一）逆元
即乘法逆元
说到逆元，基本上是为了求阶乘；之所以求阶乘，通常是为了求组合数；
数字极大时，一定需要一个MOD，这个MOD通常是100000……07之类的质数；
如果用通常的阶乘求法，非死不可；
使用扬辉三角，可以对付不少分，不过通常不是正解。
此时就需要用到逆元，或者说是乘法逆元，或者说是阶乘逆元，都是一个东西。

1）乘法逆元的定义性质：
每个数a均有唯一的与之对应的乘法逆元x，使得ax≡1(mod n)
一个数有逆元的充分必要条件是gcd(a,n)=1，此时逆元唯一存在
逆元的含义：模n意义下，1个数a如果有逆元x，那么除以a相当于乘以x。

2）费马小定理
在模为素数p的情况下，有费马小定理 a^(p-1)≡1（mod p）
那么a^(p-2) * a≡1(mod p), 也就是说a的逆元为a^(p-2)


一）A/B hdu1576　逆元模板
要求(A/B) mod 9973，但由于A很大，我们只给出n(n=A mod 9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。
Input
数据的第一行是一个T，表示有T组数据。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
Output
对应每组数据输出(A/B) mod 9973。
Sample Input
2
1000 53
87 123456789
Sample Output
7922
6060

在这题里，M==9973，与B存在gcd(B,M)==1的关系。因此B相对于9973的逆元是x.
A/B mod 9973的意义，等价于A*x mod 9973。
而(A+n) mod 9973 =n，即 A=n (mod 9973)，所以答案是n*x

解法一：扩展欧几里德，也就是求逆元
给定模数9973，求B的逆元，相当于求解Bx=1(mod 9973) ,
即存在B*x+9973*y=1的关系；y可以是任何数；
两侧取mod 9973，就得到
B*x mod 9973 =1

#include "bits/stdc++.h"
using namespace std;
const int md=9973;
typedef long long ll;
ll ex_gcd(ll a,ll b,ll &x,ll &y){
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    ll r = ex_gcd(b,a%b,y,x);
    y -= x*(a/b);
    return r;
}//扩展欧几里得模板
int main(){
    ll n,B,t,gcd,x,y;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&B);
        gcd = ex_gcd(B,md,x,y);
        x =(x*n)%md; //x=A/B,贝祖定理, n =A mod 9973
        x = (x+md) % md;
        printf("%lld\n",x);
    }
    return 0;
}

解法二：相当于解释了贝祖定理的形成。
本題由题意n=A mod 9973,
改写成n=A-A/9973*9973
因为A/B=X;所以A=n+A/9973*9973=BX;
得到 BX-9973y=n；
因为gcd(B,9973)==1，所以B*X＋9973*y==1存在x,y的整数解，
因此b*x-n一定存在正整数解，并且等于9973*n
由x*B-n=9973y，得到(x*B-n)mod 9973=0，类似《我家的门牌号》

using namespace std;  
int main()  
{  
    int t, i, j;  
    long long n, b, a=9973;  
    scanf("%d", &t);  
    while(t--)
    {  
        scanf("%lld%lld", &n, &b);  
        for(x=0; x < a; j++)  
            if((x * b - n) % a == 0) {  //b*x -n==9973*y;
                printf("%d\n", x);  
                break;  
            }  
    }  
    return 0;  
}


解法三：用费尔马小定理
#include "bits/stdc++.h"
using namespace std;
const int md=9973;
typedef long long ll;

ll powMod(ll a,ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b&1)
            ans = ans * a % md;
        a = a*a % md;
        b >>= 1;
    }
    return ans;
}

int main(){
    ll n,B,t,inv,x,y;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&B);
        inv = powMod(B,md-2);//表示i的阶乘的逆元
        x =(inv*n)%md; //x=A/B,贝祖定理, n =A mod 9973
        x = (x+md) % md;
        printf("%lld\n",x);
    }
    return 0;
}

第四个办法，递推法：
递推式如下
inv[i]=(M-M/i)*inv[M%i]%M (其中M为模数，要求为奇质数)

它的推导过程如下：
    设t=M/i,k=M%i，那么
        t*i+k≡0（Mod M）
        -t*i≡k(Mod M)
        对上式两边同时除 i×k，进一步得到
        -t*inv[k]≡inv[i](Mod M)
    再把和替换掉，最终得到
        inv[i]=(M-M/i)*inv[M%i]%M
初始化inv[1]=1，这样就可以通过递推法求出模素数的所有逆元了。

#define N 3000010
typedef long long ll;
using namespace std;
int inv[N],n,p;
int main(){
    cin>>n>>p;inv[1]=1;puts("1");
    for(int i=2;i<=n;i++){
        inv[i]=(ll)(p-p/i)*inv[p%i]%p;//因为inv[p%i]在前一个模板会变成inv[MODc[i]]，会死掉
        printf("%d\n",inv[i]);
    }
}

用到这道题上，代码本身说得通，但是由于递推数组有限制，所以，其实用不了；
参考代码：
#include "bits/stdc++.h"
using namespace std;
const int md=9973;
typedef long long ll;
int inv[1000100],n,p;
int main(){
    ll n,B,x,y;
    inv[1]=1;
    for(int i=2;i<=1000000;i++)//显然不能满足题目的要求1 < B < 1e9
        inv[i]=(md-md/i)*inv[md%i]%md;//因为inv[p%i]在前一个模板会变成inv[MODc[i]]，会死掉
    int t;cin>>t;
    while(t--){
        scanf("%lld%lld",&n,&B);
        x =(n*inv[B])%md; //x=A/B,贝祖定理, n =A mod 9973
        x = (x+md) % md;
        printf("%lld\n",x);
    }
    return 0;
}

同理换成递归，也是一个样子：B太小时，递归的次数太多，超出了系统栈的限制，程序异常退出
#include "bits/stdc++.h"
using namespace std;
const int md=9973;
typedef long long ll;
int inv(int b)
{
    if(b==1)return 1;
    return (md-md/b)*inv(md%b)%md;
}
int main(){
    ll n,B,x,y;
    int t;cin>>t;
    while(t--){
        scanf("%lld%lld",&n,&B);
        x =(n*inv(B))%md; //x=A/B,贝祖定理, n =A mod 9973
        x = (x+md) % md;
        printf("%lld\n",x);
    }
    return 0;
}


二）采用费尔马小定理，直接从阶乘与逆元，获得组合数；
using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;//质数
LL fac[1000000+5];//阶乘
LL inv[1000000+5];//逆元

LL powMod(LL a,LL b)
{
    LL ans = 1;
    while (b)
    {
        if (b&1)
            ans = ans * a % MOD;
        a = a*a % MOD;
        b >>= 1;
    }
    return ans;
}

void getFac()
{
    fac[0] = inv[0] = 1;
    for (int i = 1 ; i <= 1000000 ; i++)
    {
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = powMod(fac[i],MOD-2);//表示i的阶乘的逆元
    }
}
LL getC(LL n,LL m)        //C(n,m) = n!/((n-m)!*m!) % (1e9+7)
{
    return fac[n] * inv[n-m] % MOD * inv[m] % MOD;
}
int main()
{
    getFac();
    int n,m;
    while (~scanf ("%d %d",&n,&m))
        printf ("%lld\n",getC((LL)n,(LL)m));
    return 0;
}

三）城市建设 P6475
球球是一位建筑师。一天，他收到市长的任务：建设城市。球球打算建造 2n 座高楼。为了保证城市美观，球球做出了如下计划：
球球喜欢整齐的事物。他希望高楼从左向右排成一行，编号依次为 1～2n。
球球喜欢整数，他要求每座高楼的高度都是正整数。
由于材料限制，高楼的高度无法超过 m。
球球喜欢中间高，两边低的造型。他要求前 n 座高楼的高度不下降，后 n 座高楼的高度不上升。
球球打算选两座编号为 x,y 的高楼作为这座城市的地标。他认为只有当这两座高楼高度相等时，才会让城市变得美观。
球球把自己的想法告诉了市长。市长希望得知所有建设城市的方案数。两种方案不同，当且仅当某座高楼的高度在两个方案中不同。这个问题可难倒了球球。球球找到了你，希望你能帮他算出答案。由于答案可能很大，你只需要给出答案对 998244353 取模后的结果。

输入格式
从标准输入读入数据。
仅一行四个整数 m,n,x,y，变量意义见题目描述。
输出格式
输出到标准输出。

仅一行一个整数表示答案。
输入输出样例
输入 #1复制
3 2 1 3
输出 #1复制
10
输入 #2复制
1000 1000 535 1477
输出 #2复制
295916566
说明/提示
对于样例 1，所有的方案为：
{1,1,1,1},{1,2,1,1},{1,3,1,1},{2,2,2,1},{2,2,2,2},{2,3,2,1},{2,3,2,2},{3,3,3,1},{3,3,3,2},{3,3,3,3}。
对于 10% 的数据，1≤n,m≤5。
对于 30% 的数据，1≤n,m≤100。
对于 60% 的数据，1≤n,m≤1000。
对于 100% 的数据，1≤n,m≤10^5

分析：
这是一道组合数学的应用题
情况ABCD分类讨论，
总之最后是求阶乘，由阶乘再要求组合数，数字非常大。
如果不懂逆元的话，用杨辉三角，自求多福；
#define ll long long
#define mod 998244353
using namespace std;
int n,m,x,y;
int t;
int f[5005][5005];
int main(){
    scanf("%d%d%d%d",&m,&n,&x,&y);
    for(int i=1;i<=n+2;i++){
        f[i][1]=1;
        for(int j=2;j<=m+1;j++){
            f[i][j]=(f[i-1][j]+f[i][j-1])%mod;
        }
    }
    if(x<=n&&y>n){
        int ans=0;
        for(int i=1;i<=m;i++){
            ans=(ans+((ll)f[x][i]*f[n-x+1][m-i+1]%mod*f[y-n][m-i+1]%mod*f[n*2-y+1][i]%mod))%mod;
        }
        printf("%d",ans);
    }
    else{
        printf("%d",(ll)f[n+1][m]*f[x+n-y+1][m]%mod);
    }
    return 0;
}

逆元：用前面的模板
using namespace std;
typedef long long LL;
const LL MOD = 998244353;
LL fac[1000000+5];//阶乘
LL inv[1000000+5];//逆元
LL m,n,x,y,ans;
LL quickMod(LL a,LL b)
{
    LL ans = 1;
    while (b)
    {
        if (b&1)
            ans = ans * a % MOD;
        a = a*a % MOD;
        b >>= 1;
    }
    return ans;
}

void getFac()
{
    fac[0] = inv[0] = 1;
    for (int i = 1 ; i <= m+n ; i++)
    {
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = quickMod(fac[i],MOD-2);//表示i的阶乘的逆元
    }
}
LL getC(LL n,LL m)//C(n,m) = n!/((n-m)!*m!) % (1e9+7)
{
    return fac[n] * inv[n-m] % MOD * inv[m] % MOD;//组合数
}

LL C(LL n,LL m){return getC(m+n-1,n);}//本题组合使用的变形
int main(){
    cin>>m>>n>>x>>y;
    getFac();
    if (x <= n && y > n){
        for (int i = 1;i <= m;i++)
            ans = (ans + C(x - 1,i) * C(n - x,m - i + 1) % MOD
                * C(y - n - 1,m - i + 1) % MOD * C(n * 2 - y,i) % MOD) % MOD;
    }else ans = C(n,m) * C(n + x - y,m) % MOD;
    cout<<ans<<endl;
    return 0;
}