逆元基本知识

逆元的用处，ans = (a/b) % mod;

但是ans != (a%mod) / (b %mod)

因此我们 可以把ans 转化为 ans = a * inv（b，mod） % mod

inv(b,mod) 的含义为  b 对于 mod 的逆元 令 inv(b,mod) = x;

转化为同余方程就是 bx ≡ 1（% mod）

当 b 与 mod 互质的时候有两种方法求 inv（b,mod）

单个元素逆元

①扩展欧几里得

　　解不定方程 bx + mody = 1 其中 x的值即为 inv（b,mod）

　　学习一个 http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html

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

②费马小定理 百度百科 费马小定理

　           　

　　所以有inv(b,mod) = pow(b,p-2)

下面是一个不常用的玩意因为要保证b|a

但是当遇到b与mod不互质的情况我们有 ans = a % （mod*b） /b

                转载自 ：AC-dreamer逆元详解

1-n的逆元

　　设 t1 = mod / i ; t2 = mod % i;

　　所以我们有 t1 * i + t2 = mod

　　即 (t1 * i + t2)  ≡ 0(% mod)

　　移项 - t1 * i ≡ t2(% mod) 

　　同除 i*t2 有 -t1 * inv[t2] ≡ inv[i] & mod

      代入有 inv[i] =  kmod - mod/i * inv[mod % i] % mod ; k 为正整数 且inv[i] > 0

　　为了保证正负 不妨直接写 inv[i] =  （mod - mod/i） * inv[mod % i] % mod ;

应用：组合数逆元 

　　预处理阶乘以及阶乘逆元  转自 ： http://www.cnblogs.com/linyujun/p/5199684.html

const int N = 200000 + 5;
const int MOD = (int)1e9 + 7;
int F[N], Finv[N], inv[N];//F是阶乘，Finv是逆元的阶乘 
void init(){
    inv[1] = 1;
    for(int i = 2; i < N; i ++){
        inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
    }
    F[0] = Finv[0] = 1;
    for(int i = 1; i < N; i ++){
        F[i] = F[i-1] * 1ll * i % MOD;
        Finv[i] = Finv[i-1] * 1ll * inv[i] % MOD;
    }
}

int C(int n, int m){ 
    if(m < 0 || m > n) return 0;
    return F[n] * 1ll * Finv[n - m] % MOD * Finv[m] % MOD;
}

扩展：卢卡斯定理

 C(n, m) % p  =  C(n / p, m / p) * C(n%p, m%p) % p

LL Lucas(LL n, LL m, int p){
        return m ? Lucas(n/p, m/p, p) * C(n%p, m%p, p) % p : 1;
}