60pts

思路是二分查找每个位置跳一次后的位置，然后倍增

#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int mod=1e9+7;
int n,m,q,a[400010],s[400010];
int d1[200010][65],d2[200010][65];
signed main()
{
    // freopen("kingdom5.in","r",stdin);
    // freopen("kingdom.out","w",stdout);
    scanf("%lld%lld%lld",&n,&m,&q);
    for(int i=1;i<=n;i++)
    {
        char c;
        cin>>c;
        a[i]=c-'0';
        s[i]=s[i-1]+a[i];
    }
    for(int i=n+1;i<=2*n;i++)
        a[i]=a[i-n],s[i]=s[i-1]+a[i];
    for(int i=1;i<=n;i++)
        if(m<n)
        {
            if(s[i+m]==s[i])d1[i][0]=d2[i][0]=1;
            else
            {
                int l=i+1,r=i+m,pos;
                while(l<=r)
                {
                    int mid=(l+r)/2;
                    if(s[mid]==s[i+m])r=mid-1,pos=mid;
                    else l=mid+1;
                }
                d1[i][0]=d2[i][0]=pos-i;
            }
        }
        else
        {
            if(s[n]==0)d1[i][0]=1%n,d2[i][0]=1;
            else
            {
                int l=i+1,r=i+m%n,pos;
                while(l<=r)
                {
                    int mid=(l+r)/2;
                    if(s[mid]==s[i+m%n])r=mid-1,pos=mid;
                    else l=mid+1;
                }
                d1[i][0]=(m-(i+m%n-pos))%n,d2[i][0]=(m-(i+m%n-pos))%mod;
            }
        }
    for(int j=1;j<=60;j++)
        for(int i=1;i<=n;i++)
        {
            int nxt=(i+d1[i][j-1]-1)%n+1;
            d1[i][j]=(d1[i][j-1]+d1[nxt][j-1])%n;
            //if(i==7&&j==1)cout<<d1[i][j]<<endl;
            //if(i==1&&j==2)cout<<nxt<<" "<<d1[i][j-1]<<" "<<d1[nxt][j-1]<<" "<<d1[i][j]<<endl;
            d2[i][j]=(d2[i][j-1]+d2[nxt][j-1])%mod;
        }
    /*for(int j=0;j<=3;j++)
    {
        for(int i=1;i<=n;i++)
            cout<<d1[i][j]<<" ";
        cout<<endl;
    }cout<<endl;
    for(int j=0;j<=3;j++)
    {
        for(int i=1;i<=n;i++)
            cout<<d2[i][j]<<" ";
        cout<<endl;
    }*/
    while(q--)
    {
        int s,k;
        scanf("%lld%lld",&s,&k);
        int now=(s-1)%n+1,ans=s%mod;
        for(int i=60;i>=0;i--)
            if(k>=(1ll<<i))
            {
                k-=(1ll<<i);
                ans=(ans+d2[now][i])%mod;
                now=(now+d1[now][i]-1)%n+1;
                //cout<<i<<" "<<now<<" "<<ans<<endl;
            }
        printf("%lld\n",ans);
    }
    return 0;
}