标程-【MX-S5-T1】王国边缘

https://htoj.com.cn/cpp/oj/problem/detail?pid=22185117033728&tid=22487079604096&gid=22487067878400

#include <bits/stdc++.h>
#define ll long long
#define P 1000000007
using namespace std;
const int N = 200005;
int n, f[N][61], g[N][61], q;
ll dis[N], s, m, k;
char c[N];
int main(){
    cin >> n >> m >> q;
    cin >> c;
    int tmp = -1;
    for (int i =0; i < n; ++i)
        if (c[i] == '1') tmp = i;
    for (int i = n; i < 2 * n; ++i){
        if (c[i - n] == '1') tmp=i;
        if (tmp == -1) dis[i - n]= 0x3f3f3f3f3f3f3f3f;
        else dis[i - n] = i - tmp;
    }
    for (int i = 0; i < n; ++i){
        tmp=(i+m)%n;
        g[i][0]=max(m-dis[tmp],1ll)%P;
        f[i][0]=(i+max(m- dis[tmp],1ll))%n;
    }
    for (int j=1;j <= 60;++j)
        for (int i = 0; i < n; ++i){
            f[i][j] = f[f[i][j - 1]][j - 1];
            g[i][j] = (g[i][j - 1]+g[f[i][j - 1]][j -1]) % P;
        }
    while (q -- ){
        cin >> s >> k;
        ll ans = s % P;
        s=(s-1)%n;
        for(int j=0;j <= 60;++j)
            if ((k >> j) & 1){
                ans=(ans+g[s][j])% P;
                s=f[s][j];
            }
        cout << ans << "\n";
    }
}