Contents

1. 1. 题目：

题目：

C（排列组合的那个C）上为m，下为n，p是钥匙，输入p,n,m，求C(m,n)%p（p为很大质数）

C（m,n）= n! / [(n - m)! * m!]

#include<stdio.h>
int quick_pow(int a, int n, int p) ;
void yuchuli(int p);
int fact[10010], re_fact[10010];
int main(){

    int n, m, p;
    scanf("%d", &p);
    yuchuli(p);
    while(scanf("%d%d", &n, &m) != EOF)
        printf("%d\n", ((fact[n] * re_fact[n - m]) % p * re_fact[m]) % p);
    return 0;
}

void yuchuli(int p)         		   //预处理{

    int i;
    re_fact[0] = fact[0] = 1;
    for(i = 1; i <= 10000; i++)
    {
        fact[i] = i * fact[i - 1] % p;     //n的阶乘%p
        re_fact[i] = quick_pow(fact[i], p - 2, p); //用了费马小定理和快速幂
    }                                     //re_fact[i]是(1/i!)%p
}

int quick_pow(int a, int n, int p){

    int ans = 1;
    while(n)
    {
        if(n % 2)    			 //(n&1)
            ans = (ans * a) % p;
        a = (a * a) % p;
        n /= 2;      			 //n >>=1 或 n=n>>1
    }
    return ans;
}