You are not logged in. Please login at www.codechef.com to post your questions!

×

# Showing Wrong Answer despite of correct output.

 0 Here is my code to the question #include #include 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

 0 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. answered 04 Sep '17, 23:23 15.5k●1●20●66 accept rate: 18% @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. (05 Sep '17, 14:15) namanjn4★ 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 (05 Sep '17, 15:52) @vijju123 But it is showing wrong answer even for subtask n<10 (05 Sep '17, 19:00) namanjn4★ cause ${A_i}$ is ${10}^{9}$ even for smaller subtask (05 Sep '17, 19:22) @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. (05 Sep '17, 22:23) namanjn4★ 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 :) (05 Sep '17, 22:43) showing 5 of 6 show all
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,475
×1,664
×1,491
×856
×139
×15

question asked: 04 Sep '17, 22:11

question was seen: 941 times

last updated: 05 Sep '17, 22:43