## 【组合数求模】K – Combinations LightOJ – 1067

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
3

4 2

5 0

6 4

Sample Output
Case 1: 6

Case 2: 1

Case 3: 15

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll modn=1000003;
ll fact[modn+23]={0};
ll geta(ll n,ll& e)
{
e=0;
if(n==0) return 1;
ll res=geta(n/modn,e);
e+=n/modn;
if(n/modn%2!=0) return res*(modn-fact[n%modn])%modn;
return res*fact[n%modn]%modn;
}
ll exgcd(ll a,ll b,ll& x,ll& y)
{
ll d=a;
if(b!=0)
{
d=exgcd(b,a%b,y,x);
y-=(a/b)*x;
}
else
{
x=1;
y=0;
}
return d;
}
ll mdr(ll a,ll m)
{
ll x,y;
exgcd(a,m,x,y);
return (m+x%m)%m;
}
ll calc(ll n,ll k)
{
if(n<0||k<0||n<k) return 0;
ll e1,e2,e3;
ll a1=geta(n,e1);
ll a2=geta(k,e2);
ll a3=geta(n-k,e3);
if(e1>e2+e3) return 0;
return a1*mdr(a2*a3%modn,modn)%modn;
}
int main()
{
ll t,n,k;
fact[0]=1;
for(ll i=1;i<=modn;i++) fact[i]=(fact[i-1]*i)%modn;
scanf("%lld",&t);
for(ll i=1;i<=t;i++)
{
scanf("%lld%lld",&n,&k);
printf("Case %lld: ",i);
printf("%lld\n",calc(n,k));
}
}