simplecomplex's blog

By simplecomplex, history, 6 years ago, In English

I was trying to solve a problem on LightOJ which says to calculate C(n,r) modulo P where (1<=n,r<=1000000 and P=1000003). It has at most 2000 queries.

I found this solution on the web,but I can not find how it works. can anyone explain it please?

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N=1e6+3;
const int mod=1e6+3;
ll A[N],B[N];
ll bigmod(ll n,ll p)
{
	if(p==0)return 1LL;
	if(p&1)return ((n%mod)*bigmod(n,p-1))%mod;
	ll a=bigmod(n,p/2);
	return (a*a)%mod;
}

int main()
{
	int tc;
	scanf("%d",&tc);
	A[1]=B[1]=1;
	A[0]=B[0]=1;
	for(int i=2;i<N;++i){
		A[i]=(A[i-1]*i)%mod;
		B[i]=(B[i-1]*bigmod((ll)i,mod-2))%mod;
	}
	for(int cs=1;cs<=tc;++cs){
		int n,r;
		scanf("%d%d",&n,&r);
		printf("Case %d: %lld\n",cs,(A[n]*((B[n-r]*B[r])%mod))%mod);
	}
	return 0;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

A[i] is i! and B[i] is the inverse of i!, and therefore we use the formula C(n,r) = n!/((n-r)!(r!))? What do you not understand?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain the process of calculating inverse of i! please?.Thank you.

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it +2 Vote: I do not like it

      Read this (Modular Inverse). The method used is the binary exponentiation approach.

      How to compute the binomial coefficient using the modular inverse is also explained in the article.