各种逆元求法组合数取模 comb （组合数 Lucas）

2019-04-14 20:31发布生成海报

站内文章 / 模拟电子

12806 0

组合数取模（comb）

【问题描述】
计算C（m,n）mod 9901的值
【输入格式】
从文件comb.in中输入数据。
输入的第一行包含两个整数，m和n
【输出格式】
输出到文件comb.out中。
输出一行，一个整数
【样例输入】
2 1
【样例输出】
2 【数据规模与约定】
对于 20%的数据，n<=m<=20
对于 40%的数据，n<=m<=2000
对于 100%的数据，n<=m<=20000 题解：组合数取模(comb）
对于 20%数据：m<=20,直接计算最后取模。
对于 40%数据：m<=2000,预处理 1~2000 的逆元，暴力计算。
对于 100%数据：m<=20000,使用 lucas 定理把缩小至 9901 以内，再用上一个方
法计算。求组合数直接算阶乘肯定是不行的，会爆。（不能边算边mod，做除法是会出错）递推太慢了，舍弃。那么怎么办呢？只好又回去考虑，既然一定要取模，那么自然就想到一些在取模意义上相等的算法，要解决除法问题就剩下逆元（在模意义下将除法转为乘法）了。
逆元求法较多，下面提供几种：
（取模意义下除法 ->（ a 除以 b ）mod 一个数）
1.扩展欧几里得

inline long long extend_gcd(long long a,long long b,long long &x,long long &y){
    if(a == 0 && b == 0)
        return -1;
    if(b == 0){
        x = 1; y = 0;
        return a;
    }
    long long d = extend_gcd(b, a % b, y, x);
        y -= a / b * x;
    return d;
}

inline long long mod_reverse(long long a,long long n){
    long long d = extend_gcd(a,n,x,y);
    if(d == 1)
        return ( x % n + n ) % n;
    else
        return -1;
}

int main(){
    cin >> a >> b;
    long long nn = mod_reverse(b, mod);//逆元
    cout << a * nn % mod<< endl;
    return 0;
}

2.费马小定理（快速幂）

long long power_mod(long long z,long long y){
    long long ans = 1; z %= MOD;
    while( y ){
        if(y & 1) ans = (ans * z) % MOD;
        z = (z * z) % MOD;
        y >>= 1;
    }
    return ans;
}
int main(){
    cin >> t;
    while( t-- ){
        cin >> a >> b;
        cout << (a * power_mod(b, MOD - 2)) % MOD <return 0;
}

3.递推求阶乘逆元
a = mod / x
b = mod % x
(a*x + b) % mod = 0
a*x % mod = -b % mod
-a % mod = b * inv(x) % mod
(mod - a) % mod = b * inv(x) % mod
(mod - a) % mod * inv(b) = inv(x)

long long inva[1000005];//1--1000005的逆元 
long long MOD = 1e9 + 7, ans;

int main(){
    ans = 1;
    inva[1] = 1;
    for(int i=2; i<=1000000; i++){
        inva[i] = inva[ MOD % i ] * ( -MOD / i );
        inva[i] = ( inva[i] % MOD + MOD ) % MOD;
        ans *= inva[i];
        ans %= MOD;
    }
    cout << ans;
    return 0;
}

这样一来正常的数据就可以安安稳稳地AC了。
不过这道题，还要在优化一下–>Lucas
这里写图片描述

显然有了这个公式，我们就可以把组合数限定在MOD以内。

#include 
#include 
#include 
#include 
#define LL long long
using namespace std;

const int mod = 9901;

LL mub[10010];
LL x, y ;

void init(){//预处理阶乘
    mub[0] = 1;//注意0！ = 1
    for(int i=1; i<=10000; i++){
        mub[i] = mub[i-1] * i % mod;
    }
}

LL work( LL m , LL n ) {//递归方法，要爆栈已舍弃
    if(m == n) return 1;
    if(n == 1) return m;
    else return (work( m-1, n-1 ) + work( m-1, n )) % mod;
}

inline LL extend_gcd(LL a, LL b, LL &x, LL &y){//扩展欧几里得求逆元x
    if(a == 0 && b == 0)
        return -1;
    if(b == 0){
        x = 1; y = 0;
        return a;
    }
    LL d = extend_gcd(b, a % b, y, x);
        y -= a / b * x;
    return d;
}

inline LL mod_reverse(LL a, LL n){//规范逆元X
    LL d = extend_gcd(a, n, x, y);
    if(d == 1)
        return ( x % n + n ) % n;
    else
        return -1;
}

LL solve(LL a, LL b){
    if(a > b) return 0;//
    LL nn = mod_reverse((mub[a] * mub[(b + mod - a) % mod]) % mod, mod);
    return mub[b] * nn % mod;
}

void to_solve(LL a, LL b){//Lucas降数据
    if(b < mod){
        solve(a, b);
        return;
    }
    cout << solve(a/mod, b/mod) * solve(a%mod, b%mod) << endl;
}

int main(){
    freopen("comb.in","r",stdin);
    freopen("comb.out","w",stdout);
    LL a, b;
    cin >> b >> a;
    init();
    if(b < mod){
        printf("%lld", solve(a, b));
        return 0;
    }
    else{
        to_solve(a, b);
        return 0;   
    }
}