记录 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+1,mod=1e9+7;
int n,m,q,lst[N],f[N][64],sum[N][64];
char c[N];
signed main(){
	cin>>n>>m>>q>>c+1;
	bool flag=1;
    for(int i=1;i<=n;i++){
    	lst[i]=(c[i]-'0'?i:lst[i-1]);
    	if(c[i]-'0')flag=0;
    }
    if(flag)
    	for(int s,k;q--;)
			cin>>s>>k,cout<<(s+k)%mod<<"\n";
    for(int i=1;i<=n;i++){
    	int mm=i+m,t=mm/n,c=mm%n;
		if(t==0){
			if(lst[c]<=i)f[i][0]=i+1,sum[i][0]=1;
			else f[i][0]=lst[c],sum[i][0]=lst[c]-i;
		}
		else f[i][0]=(lst[c]==0?n:lst[c]),sum[i][0]=((n*t)%mod+lst[c]%mod-i)%mod;
    }
	for(int k=1;k<=62;k++)
		for(int i=1;i<=n;i++)
			f[i][k]=f[f[i][k-1]][k-1],sum[i][k]=(sum[i][k-1]+sum[f[i][k-1]][k-1])%mod;
	for(int s,k;q--;){
		cin>>s>>k;
		int ans=s%mod;
		s=(s-1)%n+1;
		for(int i=62;i>=0;i--)
			if(k>=(1ll<<i))k-=(1ll<<i),ans=(ans+sum[s][i])%mod,s=f[s][i];
		cout<<ans<<"\n";
	}
	return 0;
}