P11267 【MX-S5-T1】王国边缘
显然 \(m\) 一定情况下，每个点有且仅有一个将会跳到的点，这点可以预处理。
每个点都处理完之后，可以从起点开始一直跳，跳 \(k\) 步看终点，这里就可以倍增处理。
难点就在如何预处理，因为我 \(f_{i,0}\) 是在 \(i\) 点跳 \(2^0\) 步所走的距离，这个是要 \(mod 1e9+7\)，而我们是要知道我们会跳到哪个点的，即 \((i+f_{i,0})%n\)，发现模数不一样，要分开处理！！！
其次要求出每个点后 \(m\) 点最远一个 \(1\)，第一个位置的求出来，后面的也可以推出来了，首先，\(f_0\) 时可以简单 \(O(n)\) 计算（因为如果后面 \(3n\) 个都不是的话就说明看不见 \(1\)）。
查找 \(3n\) 次意味着：
-
检查了当前周期的剩余部分
-
检查了下一个完整周期
-
检查了再下一个周期的部分
否则判断 \(i+m\) 是不是 \(1\)，如果不是，则 \(fi=fi-1\)。
#include<bits/stdc++.h>
#define ll long long
#define int ll
#define ls p<<1
#define rs p<<1|1
#define re register
#define pb push_back
#define pir pair<int,int>
#define f(a,x,i) for(int i=a;i<=x;i++)
#define fr(a,x,i) for(int i=a;i>=x;i--)
#define lowbit(x) (x&-x)
using namespace std;
const int N=2e5+10;
const int M=5e6+10;
const int mod=1e9+7;
const int INF=1e9+7;
mt19937 rnd(251);char c[N];
int n,m,q;int f[N][70];
int nxt[N][70]; int r;void solve(){cin>>n>>m>>q;cin>>c;int pre=0;for(int i=0;i<n;i++){int p=(i+m);if(!i){int cnt=0;while(c[p%n]!='1'&&p!=i){p--;cnt++;if(cnt>=3*n){p=i;break;}}}else{if(c[p%n]!='1'){p=pre;}}if(p==i){p=i+1;}pre=p;nxt[i][0]=p%n;f[i][0]=(p-i)%mod;}// cout<<"\n";
//
// for(int i=0;i<n;i++){
// cout<<f[i][0]<<" ";
// }
// cout<<"\n";
// for(int i=0;i<n;i++){
// cout<<nxt[i][0]<<" ";
// }
// cout<<"\n";for(int j=1;j<=62;j++){for(int i=0;i<n;i++){int k=nxt[i][j-1];nxt[i][j]=nxt[k][j-1];f[i][j]=(f[i][j-1]+f[k][j-1])%mod;}}for(int i=1;i<=q;i++){int x,k;int g;cin>>x>>k;g=x%mod;x--;x%=n;int ans=0;int j=0;for(int j=62;j>=0;j--){if((k>>j)&1){ans+=f[x][j];ans%=mod;x=nxt[x][j];}}cout<<(g%mod+ans%mod)%mod<<"\n";}
}signed main(){
// freopen("kingdom5.in","r",stdin);
// freopen("a.out","w",stdout);ios::sync_with_stdio(0);cin.tie(nullptr); solve();return 0;
}