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;



View Code

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;
return ((a%mod)*bigmod(a,b-1,mod))%mod;

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()


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



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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s