Hello, Newbie here. I am trying to solve this problem and this is the solution i am referring to:
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
long long num[100010],pw[100010];
int main()
{
long long n,q,i,res,l,r;
string s;
cin>>n>>q;
cin>>s;
for(i=0;i<n;i++)
{
num[i+1] =num[i]+(s[i]=='0');
}
pw[0]=1;
for(i=1;i<n+5;i++)
{
pw[i] = pw[i-1]*2;
if(pw[i]>=mod) pw[i]-=mod;
}
while(q--)
{
scanf("%lld%lld",&l,&r);
res=(mod+pw[r-l+1]-pw[num[r]-num[l-1]])%mod;
printf("%lld\n",res);
}
return 0;
}
I am trying to understand the modulo used here. why does he add another mod in res. How does it help?
Thanks!
It's so that if it goes negative, it will be rectified.
C++ % operator is undefined behavior with negative number (depends on compiler). Adding mod keeps it positive while maintaining the answer.
no, it's defined behavior
I mean to say sign is implementation defined.
Since C++11 the sign of the result is well defined, not depending on implementation, see https://stackoverflow.com/questions/13100711/operator-modulo-change-in-c-11