【MX-S5-T1】王国边缘

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sint __int128
#define double long double
const int mod = 1e9 + 7;
const int len = 2e5 + 10;
int n, m, q, s, k;
string str;
sint ne[len][64];
signed main()
{
    auto mode = [&](sint num, int _mod = mod) { return (num - 1) % _mod + 1; };
    auto init = [&]() {
        string temp = " " + str + str + str;
        int rate = m / n, dist = m % n, last = -1;
        rate *= n;
        if(dist == 0 && rate)
            rate -= n, dist += n;
        for(int i = 2; i <= dist + 1; i ++)
            last = (temp[i] == '1' ? i : last);
        for(int i = 1; i <= n; i ++)
            ne[i][0] = (last + rate <= i ? 1 : last + rate - i),
            last = (temp[i + dist + 1] == '1' ? i + dist + 1 : last);
        for(int j = 1; j < 64; j ++)
            for(int i = 1; i <= n; i ++)
                ne[i][j] = (ne[i][j - 1] + ne[mode(ne[i][j - 1] + i, n)][j - 1]);
    };
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m >> q >> str;
    init();
    while(q --)
    {
        cin >> s >> k;
        sint _s = s;
        int l = 0;
        while((1ull << l) <= k) l ++;
        l --;
        while(l >= 0)
        {
            if((1ull << l) & k)
                _s += ne[mode(_s, n)][l];
            l --;
        }
        cout << (long long)(_s % mod) << endl;
    }
    return 0;
}