倍增挂成 45 求调，感谢！

https://www.luogu.com.cn/record/187590872

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
inline int read(){
    int res=0,f=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();}
    return res*f;
}
const int N=2e5+5,M=1e9+7;
int n,m,q,to[N],val[N],f[N][66],dis[N][66];
signed main(){
    n=read(),m=read(),q=read();
    string s;cin>>s,s=' '+s;
    int t=0;
    for (int i=1;i<=min(n,m);i++){
        if (s[i]=='0') continue;
        if (t==0) t=i;
        else if (m%n+1-i+(i>m%n+1)*n<m%n+1-t+(t>m%n+1)*n) t=i;
    }
    to[1]=t,val[1]=m/n;
    if (to[1]==1&&val[1]==0)
        to[1]=1+(n!=1),val[1]=(n==1);
    for (int i=2;i<=n;i++){
        if (s[(m+i-1)%n+1]=='1') to[i]=(m+i-1)%n+1;
        else if (to[i-1]==i&&val[i-1]==0) to[i]=i%n+1;
        else to[i]=to[i-1];
        val[i]=m/n+(to[i]<i);
    }
    for (int i=1;i<=n;i++){
        // cout<<to[i]<<' ';
        f[i][0]=to[i];
        dis[i][0]=val[i];
    }
    // cout<<'\n';
    // for (int i=1;i<=n;i++)
    //     cout<<val[i]<<' ';
    // cout<<'\n';
    for (int w=1;w<=62;w++)
        for (int i=1;i<=n;i++){
            f[i][w]=f[f[i][w-1]][w-1];
            dis[i][w]=(dis[f[i][w-1]][w-1]+dis[i][w-1])%M;
        }
    while (q--){
        int x=read(),k=read(),rs=0;
        rs+=(x-1)/n,rs%=M,x=(x-1)%n+1;
        for (int w=62;w>=0;w--){
            if (k<(1ll<<w)) continue;
            rs+=dis[x][w],rs%=M;
            x=f[x][w],k-=(1ll<<w);
        }
        cout<<(rs*n%M+x)%M<<'\n';
    }
    return 0;
}