Can someone help me to find out the error??
Edit: April cook off 2020 problem
You are supposed to use modular exponentition and increase i+=2 and not i++…here is my solution
https://www.codechef.com/viewsolution/32088797
in power function i have used 2*i-1
Then it might because of not using modular exponentition where we return (ans +mod)%mod…may be this might help
I couldn’t find the error. Can u check ??
Hi.
I think the error lies in your power function. When I used some large numbers to test out your power function, then the values overflow. This is probably why you are getting the wrong answer verdict.
As implemented by @mri_999, you can use modular exponentiation to calculate the powers. When I compared your codes, then there are a few differences here and there and probably that is why you are getting the issue.
You can use another function for faster calculation of power:
long long fast_power(long long base, long long power) {
long long result = 1;
while(power > 0) {
if(power % 2 == 1) {
result = (result*base) % MOD;
}
base = (base * base) % MOD;
power = power / 2; //
}
return result;
}
The complexity for the same will be O(log(power)).
Just by changing your power calculation function, your code works perfectly.
As @harsh0911 noted, your powe function is wrong.
The result for the parameters 1000, 1000 is incorrect.
It is due to res*(tem*tem)%MOD. This doesn’t work the way you expect it to and it overflows.
First it computes res*(tem*tem) and then it mods.
As all the terms can be upto 10^9+6, this will overflow.
Replacing res*(tem*tem)%MOD with res*((tem*tem)%MOD) is accpeted
Can someone tell the error please?
FastReader in=new FastReader();
int t=in.nextInt();
while(t–>0){
int n=in.nextInt();
long a=in.nextLong();
if(n==0){
System.out.println(0);
break;
}
long p[]=new long[n];
long sum=a;
p[0]=a;long h=1;
for(int i=1;i<n;i++){
a=(long)(a*p[i-1]);
p[i]=(long)Math.pow((a),h+2);
sum=sum+p[i]%1000000007;
h+=2;
}
System.out.println(sum);
}
Not getting it???