What is the mistake I have made in the question RGAME?

Here is the problem:

I don’t know what error I have made. I am getting WA for all test cases. But I get the right answers for sample test cases. I have implemented according to the editorial given.

``````#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<set>
#include<vector>
#include<utility>

#define MO 1000000007
using namespace std;

int main( ) {

int t;
cin>>t;

long long int n, a[100004],suffix_sum[100004];
long long int cost,prefix;

while ( t-- ) {
cost = 0;
cin>>n;
for ( int i = 0; i <= n; i++ ) {
scanf("%lld", &a[i]);
}

suffix_sum[n] = a[n];

for ( int i = (n-1); i >=1 ; i-- ) {
suffix_sum[i] = ( (long long int)pow(2,(n-i)) * a[i] ) % MO ;
suffix_sum[i] += suffix_sum[i+1];
}

for ( int i = 0; i <= n-1; i++ ) {
if ( i == 0 ) {
prefix = 1;
}
else {
prefix = ( (long long int)pow(2,(i-1)) *  a[i] ) % MO;
}
cost += ( (prefix * suffix_sum[i+1]) % MO );
}
cout<<2*cost<<endl;
}
return 0;
}``````
1 Like

I am guessing that the built in pow() function for double/float exponentiation is causing some loss of precision. By definition, floats and doubles have limited precision. Try doing modular exponentiation by squaring. There are many implementations/tutorials online.

Here is my implementation, hopefully it will get you an AC

``````// modpow(n, k) = n ^ k % MOD where MOD = 1e9+7
long long modpow(long long n, long long k) {
long long r = 1;
while (k > 0) {
if (k % 2 == 1)
r = (r * n) % MOD;
n = (n * n) % MOD;
k /= 2;
}
return r;
}
``````

if you have any questions, feel free to ask.

The time complexity of the function is O(log(n)) if you are wondering It uses divide and conquer technique.

Hi, thanks for your suggestion. I tried replacing the pow function with the modpow function provided by you. But I still get WA. Any other ideas?