BZOJ2982——combination

1、题意：求 C(n,m) % 10007 ,10007是质数咯 n和m < 2000000000

2、分析：这个东西太大了，显然不能用n!的阶乘预处理的方式搞出来，也不能用递推公式搞出来

于是我们直接lucas定理 C(n,m) % MOD = C(n / MOD, m / MOD) * C(n % MOD, m % MOD) % MOD

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 10010
#define MOD 10007

inline int read(){
    char ch = getchar(); int x = 0, f = 1;
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while('0' <= ch && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int fac[M], inv[M];

inline void init(){
    fac[0] = 1;
    for(int i = 1; i < MOD; i ++) fac[i] = fac[i - 1] * i % MOD;
    inv[1] = 1;
    for(int i = 2; i < MOD; i ++) inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
    inv[0] = 1;
    for(int i = 1; i < MOD; i ++) inv[i] = inv[i] * inv[i - 1] % MOD;
}

inline int C(int n, int m){
    if(n < m){
        return 0;
    }
    if(n < MOD && m < MOD){
        return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
    }
    return C(n / MOD, m / MOD) * C(n % MOD, m % MOD) % MOD;
}

int main(){
    int T = read();
    init();
    while(T --){
        int n = read(), m = read();
        printf("%d\n", C(n, m));
    }
    return 0;
}

巴特西

BZOJ2982——combination

最新文章

热门文章