Showing Wrong Answer despite of correct output.

general
, , , , ,
1

Here is my code to the question

#include<stdio.h>
#include<math.h>
    long int A[100005];
    long int sum;
int main(){
   int t,n,i,j;
   scanf("%d",&t);

   while(t--){
        sum=0;

        scanf("%d",&n);
        for(i=0;i<n+1;i++)
            scanf("%ld",A+i);
        for(i=0;i<=n;i++){
            for(j=i+1;j<=n;j++){
                if(i!=0){

                sum=sum+(A[i]*A[j]*pow(2,n+i-j));
                }
                if(i==0)
                    sum=sum+(A[i]*A[j]*pow(2,n+1-j));

            }
        }
        printf("%ld\n",sum);
   }
}

Please help me to find the fault in my code.

2 
 sum=sum+(A[i]*A[j]*pow(2,n+i-j));

n in range of upto {10}^{5} is bound to give you overflow (and hence WA) in sum=sum+(A[i]*A[j]*pow(2,n+i-j));

Read up fast exponentiation, or store the power of 2%mod in an array and use accordingly.

3

@vijju123 In the question there is a line that say:
Since the answer can be very large, print the answer modulo 10∆9 + 7.
What does it mean.

4

It means that answer can be as large as {2}^{100000} . Since we cannot store such numbers in conventional data types, we take remainder of the number when divided by {10}^{9}+7. Read about properties of % operator. The multiplication and addition properties of it (i.e. (a+b)%m=(a%m+b%m)%m and a*b%m=((a%m)*(b%m))%m can prevent overflow issues. What we have to do is, that at every step, every time we update sum, we do sum%mod , where mod = {10}^{9}+7. It is just a random large number given to make sure you dont suffer overflow. Since we do sum%mod at every step, it never exceeds mod

5

@vijju123 But it is showing wrong answer even for subtask n<10

6

cause {A_i} is {10}^{9} even for smaller subtask

7

@vijju123 can you please guide me how should i update my code to get it solved.I have tried some changes but its still showing wrong answer.

8

Its best to look at editorialist’s solution first, because I havent attempted the question yet. If a doubt persists after that, I will happily help :slight_smile: