Article From:https://www.cnblogs.com/mch5201314/p/9970927.html
Subject Meaning
Give you a string of n characters (0 or 1). When you go to a certain position, all the remaining positions are added with the number of that position. Query the l, r intervals Q times.
After the operation, what is the final sum? Take the model for 1e9 + 7?
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf=1e9+7;
ll sum[1000005];
ll pow(ll a,ll b,ll n){
ll ans=1;
ll base=a;
while(b){
if(b&1) ans=ans*base%n;
base=base*base%n;
b>>=1;
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll n,q;
char s[1000005];
//freopen("in.txt","r",stdin);
while(cin>>n>>q){
cin>>s+1;
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++)
if(s[i]=='1') sum[i]=sum[i-1]+1;
else sum[i]=sum[i-1];
int l,r;
while(q--){
ll ans=0;
cin>>l>>r;
ans=pow(2ll,sum[r]-sum[l-1],inf)-1;
ans=(ans+(ans*(pow(2ll,r-l+1+sum[l-1]-sum[r],inf)-1))%inf)%inf;
cout<<ans<<endl;
}
}
return 0;
}
Link of this Article: C. Banh-mi