1067: Combinations

We all know the formula of nCr =n!/(r!*(n-r)!)

it’s a general formula,but this problem is about nCr %mod

it can be done with Modular multiplicative inverse 

formula of nCr % mod is (f(n)%mod*(((r)^(mod-2))%mod*((n-r)^(mod-2))%mod)%mod;

here we need to calculate the result using bigmod function;

References

 

View Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[1000005];
const int mod = 1000003;
ll bigmod(ll a,ll b,ll mod)
{
if(b==0) return 1;
if(b&1)
{
return ((a%mod)*bigmod(a,b-1,mod))%mod;

}
else{
ll x=bigmod(a,b/2,mod);
return (x%mod*x%mod)%mod;
}

}

ll inverseEuler(ll a,ll b)
{
return bigmod(a,b-2,b);
}
int main()
{

dp[0]=dp[1]=1;

for(ll i=2;i<=1000000;i++) dp[i]=((dp[i-1]*i)%mod); ll n,k; ll cs=1,t; cin>>t;
while(t–)
{cin>>n>>k;
ll res=((dp[n]%mod)*(inverseEuler(dp[k],mod)*inverseEuler(dp[n-k],mod))%mod)%mod;
printf(“Case %lld: %lld\n”,cs++,res);
}
}

 

Advertisements

About waprogramming

I am in CSE,from CUET
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s