LightOJ - 1067 Combinations

朴灿烈づ我的快乐病毒、 2022-06-13 11:29 139阅读 0赞

#                                              Combinations     #

Given **n** different objects, you want to take **k** of them. How many ways to can do it?

For example, say there are 4 items; you want to take 2 of them. So, you can do it 6 ways.

**Take 1, 2**

**Take 1, 3**

**Take 1, 4**

**Take 2, 3**

**Take 2, 4**

**Take 3, 4**

Input

Input starts with an integer **T (≤ 2000)**, denoting the number of test cases.

Each test case contains two integers **n (1 ≤ n ≤ 106), k (0 ≤ k ≤ n)**.

Output

For each case, output the case number and the desired value. Since the result can be very large, you have to print the result modulo **1000003**.

Sample Input

4 2

5 0

6 4

Sample Output

Case 1: 6

Case 2: 1

Case 3: 15

这是一道基础数论题，组合数取模。题意就是输入一个n表示有n组测试数据，然后输入a,b(1<=b<=a<=1e6)，求a,b的组合数C(a,b)模1000003后的值，并按格式输出。这道题要用到Lucas定理。

首先给出这个Lucas定理：  
A、B是非负整数，p是质数。AB写成p进制：A=a\[n\]a\[n-1\]...a\[0\]，B=b\[n\]b\[n-1\]...b\[0\]。  
则组合数C(A,B)与C(a\[n\],b\[n\])\*C(a\[n-1\],b\[n-1\])\*...\*C(a\[0\],b\[0\])  modp同余  
即：Lucas(n,m,p)=c(n%p,m%p)\*Lucas(n/p,m/p,p)

一般对于大组合数取模，a,b不大于10^5的话，用逆元的方法，可以解决。对于a,b大于10^5的话，要求p<10^5，这样就是Lucas定理了，将a,b转化到10^5以内解。而这题a,b,p虽然都大于10^5，但也没有大太多，依然可以用Lucas定理来解决，以下就是AC代码。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <algorithm>
    #include <set>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 1e6 + 5;
    const int MOD = 1e9 + 7;
    const double eps = 1e-7;
    const double PI = acos(-1);
    using namespace std;
    
    LL quick_mod(LL a, LL b, LL c)//费马小定理+快速幂求逆元
    {
    	LL ans = 1;
    	while (b)
    	{
    		if (b%2==1)
    			ans = (ans*a) % c;
    		b /=2;
    		a = (a*a) % c;
    	}
    	return ans;
    }
    
    
    LL fac[MAXN];
    void Get_Fac(LL m)//阶乘打表
    {
    	fac[0] = 1;
    	for (int i = 1; i <= m; i++)
    		fac[i] = (fac[i - 1] * i) % m;
    }
    LL Lucas(LL n, LL m, LL p)//卢卡斯定理
    {
    	LL ans = 1;
    	while (n && m)
    	{
    		LL a = n % p;
    		LL b = m % p;
    		if (a < b)
    			return 0;
    		ans = ((ans*fac[a] % p) * (quick_mod(fac[b] * fac[a - b] % p, p - 2, p))) % p;
    		n /= p;
    		m /= p;
    	}
    	return ans;
    }
    
    
    int main()
    {
    	int a, b;
    	int T;
    	scanf("%d", &T);
    	Get_Fac(1000003);
    	for (int i = 1; i <= T; i++)
    	{
    		scanf("%d%d", &a, &b);
    		printf("Case %d: %d\n", i, Lucas(a,b, 1000003));
    	}
    }