TLE in DEMENTIA14 MULFACT

general
,
1

I have submitted the solution for the problem MULFACT but it got TLE.Here’s my code :

#include<`bits/stdc++.h`>
using namespace std;
#define MOD 329885391853
#define LL unsigned long long

LL N,i,P,F;
long T;

LL mulMod(LL A,LL B)
{
	LL R=0LL;
    
	while(A!=0)
	{
		if(A&1)
		R=(R+B)%MOD;
		
		A>>=1;
		B=(B<<1)%MOD;
	}
	
	return R;
}

LL Fact[999945]={1LL};

LL Pro[999945]={1LL};

void precalc()

{

	Fact[1]=1LL;
    
	Pro[1]=1LL;
    
	for(i=2LL;i<=999982LL;i++)
	{
		Fact[i]=(Fact[i-1]*i)%MOD;
    
		Pro[i]=mulMod(Pro[i-1],Fact[i]);
	}
}

int main() 
{
	precalc();
    
	scanf("%ld",&T);
    
	while(T--)
	{
    
		F=1LL,P=1LL;
		scanf("%llu",&N);
		if(N>=999983)
		printf("0\n");
		else

{

printf("%llu\n",Pro[N]);

}
    

}

return 0;

}

Is there any way to optimise it?

2

@knb_dtu yes same thing happened with me as well,solution gave TLE in C++ 4.3.2 and AC in C++ 4.8.1.

3

same thing happened to me but i guess it would have bee wiser to store the factorials and the fact(m) value till 999983…many people did it that way

4

Also u can modify you multMod function … complexity of the mulmod function can be reduced … have a look at this solution for more information… http://www.codechef.com/viewsolution/3501807

2 Likes