XidianOJ 1032 找规律Ⅱ

题目描述

现有数阵如下：

求这个数阵的第n行m列是多少（行列标号从1开始）

结果对10007取模

输入

多组数据，每组数据一行，包含两个整数n,m（1<=n<=m<=10^18）

输出

每组数据输出一行，为数阵中第n行m列对10007取模后的值。

--正文

C(m,n) % p 

组合数取模问题

PS：找规律真是恶心

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
LL n,m;
LL p = 10007;

LL quick_mod(LL a,LL b){
    LL ans = 1;
    a %= p;
    while (b){
        if (b & 1){
            ans = ans * a % p;
        }
        b >>= 1;
        a = a * a % p; 
    }
    return ans;
}

LL C(LL n,LL m){
    if (m > n) return 0;
    LL ans = 1;
    LL i;
    for (i=1;i<=m;i++){
        LL a = (n + i - m) % p;
        LL b = i % p;
        ans = ans * (a * quick_mod(b,p-2) % p) % p; 
    }
    return ans;
}

LL lucas(LL n,LL m){
    if (m == 0) return 1;
    return C(n % p,m % p) * lucas(n / p,m / p) % p;
} 
int main(){
    while (scanf("%lld %lld",&n,&m) != EOF){
        printf("%d
",lucas(m,n));
    }
    return 0;
}