HELP WITH FACTORIAL PROBLEM!

Revision en3, by om1429888, 2022-08-16 15:15:29

((3 * ‘N’ ) ! / ( 3! ^ ‘N’ ) )% ‘P

I HAVE TO SOLVE THIS. THE PROBLEM IS IF N=4; AND P=7 MY NUMERATOR BECOMES 0 AND THIS WILL GIVE ME WRONG ANSWER. THE ANSWER IS 6 BUT MY CODE IS GIVING 1.

THIS IS HOW IM DOING IT. IM ITERATING FROM 1 TO 3*N CALCULATING (3*N)FACTORIAL. CALCULATE THE DENOMINATOR, DO MOD INVERSE AND MULTIPLY. ANY SUGGESTIONS HOW CAN I DEAL WITH THIS.

#include <bits/stdc++.h>
#define ll long long
ll factorial(ll n,ll p){
ll res=1;
for(ll i=1;i<=n;i++){
res=((res%p)*(i%p))%p;
}
return res;
}
ll power(ll num,ll d,ll p){
ll res=1;
while(d){
if(d&1){
res=((res%p)*(num%p))%p;
d--;
}
d/=2;
num=((num%p)*(num%p))%p;
}
return res;
}
ll mul(ll a,ll b,ll p){
ll res=0;
a%=p;
while(b){
if(b&1){
res=((res%p)+(a%p))%p;
b--;
}
b/=2;
a=(2*(a%p))%p;
}
return res;
}
long long int factorialAgain(long long int n,long long int p)
{
if(p==1)return 0;
ll temp=3*n;
ll numerator=factorial(temp,p);
n%=(p-1);
ll den=power(6,n,p);
ll inverse=power(den,p-2,p);
ll ans=mul(inverse,numerator,p);
return ans;
}


#### History

Revisions

Rev. Lang. By When Δ Comment
en3 om1429888 2022-08-16 15:15:29 29
en2 om1429888 2022-08-16 15:14:49 7 Tiny change: ' res=((res)*(i));\n }\n' -> ' res=((res%%p)*(i%p))%p;\n }\n'
en1 om1429888 2022-08-16 15:14:02 1385 Initial revision (published)