大组合数取模

大组合数取模

线性求逆元

。。。。。。

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
const int N = 3e6 + 10;

#define LL long long
#define lgj 1000000007

LL jc[N], inv[N], Inv[N];
LL n, k;

inline LL read(){
    LL x = 0; char c = getchar();
    while(c < '0' || c > '9') c = getchar();
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x;
}

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

inline void work_1(){
    LL x, y;
    exgcd((jc[k] * jc[n - k]) % lgj, lgj, x, y);
    while(x < 0) x += lgj;
    LL answer = (jc[n] * x) % lgj;
    printf("%lld", answer);
    exit(0);
}

inline LL ksm(LL x, LL y){
    LL ret = 1;
    while(y){
        if(y & 1) ret = ret * x % lgj;
        x = x * x % lgj;
        y >>= 1;
    }
    return ret;
}

inline void work_2(){
    LL x = ksm((jc[k] * jc[n - k]) % lgj, lgj - 2);
    LL answer = (jc[n] * x) % lgj;
    printf("%lld", answer);
    exit(0); 
}

inline void work_3(){
    inv[1] = inv[0] = 1; Inv[0] = Inv[1] = 1;
    for(int i = 2; i <= n; i ++)
    {
        inv[i] = (1LL * (- (lgj / i)) * inv[lgj % i]) % lgj;
        if(inv[i] < 0) inv[i] += lgj;
        Inv[i] = (Inv[i - 1] % lgj * inv[i] % lgj) % lgj;
        if(Inv[i] < 0) Inv[i] += lgj;
    }    
    LL answer = ((jc[n] % lgj * Inv[k] % lgj) % lgj * Inv[n - k] % lgj) % lgj;
    printf("%lld", answer);
}

inline void work_4(){
    
    inv[1] = inv[0] = 1;
    for(int i = 2; i <= n; i ++)
    {
        inv[i] = ((1LL * (- (k / i))) * inv[k % i]) % k;    
        if(inv[i] < 0) inv[i] += k;
    }
    for(int i = 1; i <= n; i ++) printf("%lld
", inv[i]);
}

int main()
{
    n = read();
    k = read();
    jc[1] = 1;
    for(int i = 2; i <= n; i ++) jc[i] = (jc[i - 1] * (i % lgj)) % lgj;
    work_1();//exgcd 求解 C(n, k) % lgj 
    work_2();//ksm   求解 C(n, k) % lgj
    work_3();//线性求阶乘逆元  求解 C(n, k) % lgj .. inv[i] i 在 % lgj 意义下的逆， Inv[i] 阶乘的逆，也就是将逆阶乘
    work_4();//求 1 ` n 在 % k 意义下的逆
    
    return 0;
}