Why I’m getting TLE in BINTOUR while submitting in scala?
(Link for scala submission-http://www.codechef.com/viewsolution/3937151)
object Main
{
var Fact=new Array[Int](1000005)
var InvFact=new Array[Int](1000005)
var MOD=1000000009
def modPow(P:Int,Q:Int):Int=
{
var X=1
var A=P
var B=Q
while(B>0)
{
if(B%2==1)
{
X=(X*A)%MOD
A=(A*A)%MOD
B=B/2
}
}
X
}
def GenerateFactorial():Unit=
{
Fact(0)=1
Fact(1)=1
Fact(2)=2
for(i<-3 until 1000002)
{
Fact(i)=(Fact(i-1)*i)%MOD
}
}
def InverseMod(A:Int):Int=
{
modPow(A,MOD-2)
}
def GenerateInverse():Unit=
{
InvFact(0)=1
InvFact(1)=1
for(i<-2 until 1000002)
{
InvFact(i)=InverseMod(Fact(i))
}
}
def C(N:Int,R:Int):Int=
{
var Comb=1
Comb=Fact(N)*InvFact(R)
Comb=Comb%MOD
Comb=Comb*InvFact(N-R)
Comb=Comb%MOD
Comb
}
def main(args:Array[String])
{
GenerateFactorial()
GenerateInverse()
var N=readInt()
var P=1<<N
P=P-1
for(i<-0 until P)
{
if(i<((P/2)-1))
{
println("0")
}
else
{
var sol=1L
sol=(sol*Fact(P/2)*2)%MOD
sol=(sol*C(i,P/2-1))%MOD
sol=(sol*Fact(P/2))%MOD
println(sol)
}
}
}
}
The same solution when submitted in C++ got me AC
Link of submission in C++:-
http://www.codechef.com/viewsolution/3541422