求调 WA #6 #10

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5;
int sum[N*2];
int nxt[N][65];//s[i]到下一个需走多少步(这玩意也要倍增) 
int u[N][65];//S[i]跳j步到哪 
const int maxk=60;
const int mod=1e9+7;
int pos[N];
int main(){
	//freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n,q;ll m;string S;
	cin>>n>>m>>q>>S;
	S=' '+S;
	//相当于S=S+S 
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+(S[i]=='1'?1:0);
	for(int i=n+1;i<=2*n;i++) sum[i]=sum[i-1]+(S[i-n]=='1'?1:0);
	
	int p1=0;//S中最后一个1的位置 
	for(int i=n;i>=1;i--) if(S[i]=='1'){
		p1=i;break;
	}
	pos[0]=-1;
	for(int i=1;i<=n;i++){
		if(S[i]=='1') pos[i]=i;
		else pos[i]=pos[i-1];
	}
	
	ll lst=-1;//上一个1的位置或无1时最后一个0的位置 
	for(int i=1;i<=n;i++){
		ll r=min(2ll*n,i+m);
		if(sum[r]-sum[i]==0){
			nxt[i][0]=1;//全0 
			lst=i+m;
			u[i][0]=i+1;
			if(u[i][0]>n) u[i][0]=1;
		}
		else{
			//找出离S[i]最远的1 
			
			int tmp=(i+m)%n;if(tmp==0) tmp+=n;
			if(pos[tmp]>0){
				lst=i+m-tmp+pos[tmp];
				u[i][0]=pos[tmp];
				nxt[i][0]=(lst-i)%mod;
			}
			else{
				lst=i+m-tmp-n+p1;
				nxt[i][0]=(lst-i)%mod;
				u[i][0]=lst%n+(lst%m==0?n:0);
			}
		}
	}
	for(int j=1;j<=maxk;j++){
		for(int i=1;i<=n;i++){
			u[i][j]=u[u[i][j-1]][j-1];
		}
	}
	/*
	for(int j=0;j<=2;j++){
		cout<<"j="<<j<<endl;
		for(int i=1;i<=n;i++) cout<<u[i][j]<<' ';
		cout<<endl;
	}
	*/
	for(int j=1;j<=maxk;j++){
		for(int i=1;i<=n;i++){
			nxt[i][j]=(nxt[i][j-1]+nxt[u[i][j-1]][j-1])%mod;
		}
	}
	/*
	for(int j=0;j<=2;j++){
		cout<<"j="<<j<<endl;
		for(int i=1;i<=n;i++) cout<<nxt[i][j]<<' ';
		cout<<endl;
	}
	*/
	
	while(q--){
		ll s,k;
		cin>>s>>k;
		if(k==0){
			cout<<s%mod<<endl;
			continue;
		}	
		ll ts=s%n;
		if(ts==0) ts+=n;
		int step=0;
		for(int j=maxk;j>=0;j--){
			//cout<<"j="<<j<<' ';
			ll tmp=1ll<<j;
			//assert(tmp>0);
			if(k>=tmp){
				step=(step+nxt[ts][j])%mod;
				ts=u[ts][j];
				k-=tmp;
			}
			//cout<<step<<endl;
		}
		cout<<(s%mod+step)%mod<<endl;
	}
	return 0;
}
//预处理在S上每个位置一步向前走几格 
//k非常大,要倍增 
/*
8 3 1
10001011
1 2
*/