1067 - Combinations

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1067

Solution Idea : ans is nCr. which is n!/r!(n-r)! .  as n and k is below <=10^6. so first we store the value of factorial 1 to 10^6 mod 1000003 in fact array.

then for finding n!/r!(n-r)! we need to find the modular inverse of r!(n-r)!. then ans is( n! * modular inverse of r!(n-r)!) mod 1000003.

Solution :

#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll int X=-1,Y=-1;

ll int ext_gcd ( ll int A,ll int B)
{
    ll int x2, y2, x1, y1, x, y, r2, r1, q, r;
    x2 = 1;
    y2 = 0;
    x1 = 0;
    y1 = 1;
    for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y )
    {
        q = r2 / r1;
        r = r2 % r1;
        x = x2 - (q * x1);
        y = y2 - (q * y1);
    }
    X = x2;
    Y = y2;

    return r2;
}

ll int minv(ll int a,ll int m)
{
    ext_gcd(a,m);

    X=X%m;

    if(X<0) X=X+m;

    return X;
}


ll int fact[1000001];
ll int m=1000003;

int main()
{
    fact[0]=1;

    for(ll int i=1; i<=1000000; i++)
    {
        fact[i]=((fact[i-1]%m)*(i%m))%m;
    }

    ll int t,n,r,ans;

    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld%lld",&n,&r);

        ans= ((fact[r]%m)*(fact[n-r]%m))%m;
        ans=minv(ans,m);
        ans=(fact[n]*ans)%m;
        printf("Case %lld: %lld\n",ca,ans);
    }

}