1067 – Combinations—LightOj（Lucas求组合数）

题目链接：http://lightoj.com/volume_showproblem.php?problem=1067

模板求C(n,m)%p, Lucas模板;

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <math.h>using namespace std;#define met(a, b) memset(a, b, sizeof(a))
#define N 1000953
#define INF 0x3f3f3f3f
const int MOD = ;typedef long long LL;LL f[N];LL Pow(LL a, LL b)
{
    LL ans = ;
    while(b)
    {
        if(b&)
            ans = ans*a%MOD;
        b>>=;
        a = a*a%MOD;
    }
    return ans;
}LL C(LL n, LL m)
{
    if(m == )return ;
    if(m > n)return ;
    /*
    LL ans = 1;
    for(int i=1; i<=m; i++)
    {
        LL a = (n-m+i);
        LL b = i;
        ans = ans*(a*Pow(b, MOD-2)%MOD)%MOD;
    }这样会超时，所以要预处理阶乘；
    */
///C(n, m) = n!/(m!(n-m)!)%MOD--->n!/m!%MOD * 1/((n-m)!)%MOD;
///   a/b%MOD == a*b^(MOD-2)%MOD;
    LL ans = f[n]*Pow(f[m], MOD-)%MOD * *Pow(f[n-m], MOD-) % MOD;    return ans;
}void Fact(LL n)
{
    f[] = ;
    for(int i=; i<=n; i++)
        f[i] = f[i-]*i%MOD;}int main()
{
    Fact(MOD);
    int T, t = ;
    LL n, k;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%lld %lld", &n, &k);
        LL ans = C(n, k);
        printf("Case %d: %lld\n", t++, ans);
    }
    return ;
}