Why my answer is not accepted

general
1

The link to the question is RGAME Problem - CodeChef. I tried my code in terminal it gave the correct answer for all the cases I tried. But here it shows wrong answer. Can anyone plz tell what is the problem and which case it is not working for?
my code is :

 #include<iostream>
        #include <math.h>  
        using namespace std;  
        long long power(long long a,long long b)    
        {  
        	long long c=pow(a,b);  
        	return c;  
         }  
    
     int main()  
        {  
        	int t;  
        long long int  M=1000000007;  
        	cin>>t;  
        	while(t--)  
        	{  
        	long long	int n;  
        		cin>>n;  
        	long long	int a[100002];  
        		for(long long int i=0;i<=n;i++)  
        		cin>>a[i];  
        	 long long int sum=0;  
        		for(long long int k=0;k<n;k++)  
        		{  
        			for(long long int p=k+1;p<n+1;p++)  
        			{  
        		if(k==0)  
        		sum=(sum+((power(2,n-p+1))%M*a[k]*a[p]%M)%M)%M;  
        		else sum=(sum+( power(2,k))%M*(power(2,n-p))%M*(a[k]*a[p])%M)%M;  
        				
        		}  
        		}  
        		cout<<sum<<"\n";  
        	}  
        	return 0;}
2

Thats because N can be upto 10^5, and you just cant calculate 2^(100000) by simple pow function. You will get a immediate overflow, and hence WA.

Try searching for fast exponentiation, thats what you exactly need. Or, alternatively, you can try storing (powers of 2)%M in an array. Like-

power_two[i]=(power_two[i-1]*2)%m;
3

Your code will cause overflow for large value of n.

long long int can only hold numbers till 2^64.

Look at the constraints on n = 10 ^ 5.
So when you calculate pow(2, x), for such large x, pow function will cause integer overflow.

You need to use something else instead of inbuilt pow function.
Maybe Modular exponentiation or precomputation of powers of 2.

Look at the way how are powers of two are precomputed avoiding overflow in Author’s solution.

You can refer this thread as well.

4

Helpful… But it didn’t rectify the problem. There is something more wrong in my code. Otherwise, it should have worked for small subtask where N<=10.

5

Even for n<=10, array elements can be as large as 10^9. Make sure you are not suffering from overflow. Also, as @sumedhk said, give a look to editorial. Have you got the formula right?