# TLE in DEMENTIA14 MULFACT

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?

@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.

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

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