×

# CHKSEL - Editorial

 0 PROBLEM LINK : contest practice Author : Rahul Agarwal Tester : Rahul Agarwal Editorialist : Rahul Agarwal DIFFICULTY : Medium-Hard PREREQUISITES : Number Theory, Lucas Theorem PROBLEM : Find the number of ways of selecting K distinct items from a group of N distinct items. As the output can be large print the answer modulo P. Flawed Code : #include #define ll long long ll fact[1000000]; int pwr(int x,int p,int mod){ ll t = 1,a=x; while(p) { a=(a*a)%mod;p=p>>1; } return t;} ll abc(int n,int r,int MOD){ ll tem=(fact[r]*fact[n-r])%MOD; tem=pwr(tem,MOD-1,MOD); return (tem*fact[n])%MOD;} ll xyz(ll n,ll m,int p){ if(n==0)return 1; if(m==0)return 1; int ni=n%p; int mi=m%p; return xyz(n/p,m/p,p)*abc(ni,mi,p)%p;} ll C(ll n,ll r,int MOD){ fact[0]=1; for(int i=1;i!=MOD;i++) fact[i]=(i*fact[i-1])%MOD; return xyz(n,r,MOD);} int main(){ int t;cin>>t; while(t--){ ll n,k;int p; cin>>n>>k>>p; printf("%lld",C(n,k,p)); }} EXPLANATION : This question was a simple implementation of the Lucas Theorem The corrected code can be view at, Corrected Code. This question is marked "community wiki". asked 30 Mar '16, 20:36 11●1 accept rate: 0% 0★admin ♦♦ 19.8k●350●498●541
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,303
×900
×639
×34
×6
×1

question asked: 30 Mar '16, 20:36

question was seen: 767 times

last updated: 01 Apr '16, 16:46