using namespace std;
const unsigned int M = 1000000007;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
l n ; cin >>n;
l sum=0;
for ( l i = 0 ; i < n ; i++ ){
l var; cin >> var ;
if ( var<0){
sum+=(var%M+M)%M;
}
else{
sum+=var%M;
}
sum= sum%M;
}
l q; cin >> q;
for ( l j=0 ; j <q; j++){
sum+=sum;
sum = sum%M;
cout << sum<<endl;
}
We want to output the answer in modulo field of MOD 10^9+7. So any number outside that range shall correspond to one value in range [0, 10^9+6].
For some x, we want to find y such that x = y + c*MOD and y \in [0, 10^9+6]. It can be see that for each x, there’s a unique y and c. You’d need to read on modular arithmetic, here and here
My idea for bonus problem is that since range [L, R] would be something like suffix of a rotation of A + Rotations of array A repeated X times for some X \geq 0 + prefix of a rotation A. There can also be a case where [L, R] correspond to a subarray of a rotation of A.
The sum of middle part is fixed. We need to determine the rotation of A which covers position L and R. This is the tricky part. Something like divide and conquer is possible here. It’d take time proportional to the number of times the array size is doubled.
Since array length doubles after each operation, and we want to keep L and R in long long range, there cannot be more than 64 queries of first type. Let’s call that Q_1
Hence, the solution would be working in something like O(Q_1) for each query of second type.
Hello friend!! actually logically ans for negative sum doesnt make any sense at all.You have to blindly follow the logic for negative no. Hope that helps!!!
bro question tells us to find mod 10^9 + 7 hence for negative values we have to use that logic only. dont think about the ans if it is making any logic or not . u have to just use mod concept for negative no . That’s it!!! XD
Can anyone tell why it is showing TLE, when I directly perform modulo 10^9 +7)?
Also, please help me by telling what is the most efficient way of doing it.
i am new to codechef and cp
i know the code for this because i saw others submission and also got correct ans while submitting but i want to know why are we doing this ?
sum = ((sum % MOD) + MOD) % MOD;
why do we need to % + % 1000000007
cant we just add the initial sum of the array and then again keep adding q times
sum=sum+sum;
and then at the end
cout<<abs(ans)%1000000007;
@nk20422 why is -8 mod 5 is equal to 2 why not -3 or 3(positive) wherein 8 mod 5 is equal to 3
please can someone please help me in clearing my doubt
thank you in advance
In c++ if you take modulo of a negative number you will get a negative result which is in sync with the mathematical way of doing modulo operation but for the purpose of the problem, we have to convert the mod result in the range [0,n-1]. We can do this either by initially adding a multiple of the divisor to the number such that the resultant sum will be positive and then take the mod but that’s not the efficient way as it will take more steps rather we use the above-mentioned way. Now taking your example of -8 mod 5, either you can add
(5*2 + (-8)) mod 5 = 2
the main problem here is you have to run few steps to find the least divisor multiple which will make the sum positive which in this case is 2.
now use the above method.
-8 mod 5 = -3
(-3 + 5 ) mod 5 = 2.
I hope I haven’t messed it up a lot but this is what I can come up with the simplest explanation
mod = 10**9 + 7
n = int(input())
arr = list(map(int, input().split()))
q = int(input())
temp = list(map(int, input().split()))
total = sum(arr)
for _ in range(q):
total = total*2 % mod
print(total)
@sarvdeep_mark
thank you so much for replying
i understood we need to make the negative ans into positive since we cannot take modulo for negative values
but while making the negative into positive why cant we just use abs(-ans)
for example abs(-8) mod 5 = 3
and 3 comes within 0 to n-1(0 to 5 in above eg)
abs(-1000000008) % 1000000007
=1
here also mod ans will always be in between 0 to 1000000007-1
