标题

题解 -【MX-S5-T1】王国边缘

题目链接：P11267 【MX-S5-T1】王国边缘

约定记号 $S^c$ 表示字符串 $S$ 循环 $c$ 次拼接而成的字符串。特别地，若 $c = \infty$，则表示字符串 $S$ 无限循环拼接而成的字符串。

题目描述

异客在一个无限循环的 $\texttt{01}$ 字符串 $T=S^\infty$ 上进行着他的旅程，其中 $S$ 的长度为 $n$，$T$ 的第 $i$ 个字符为 $T_i$。

异客的视野有限，只能看到后面 $m$ 个字符。

异客会进行 $q$ 次旅程，每次起点不同，移动次数也不同。

当异客在 $T_i$ 上时：

• 若 $T_{i+1\dots i+m}$ 中存在 $\texttt{1}$，则异客下一次会移动到其中最远的一个 $\texttt{1}$ 上。
• 否则，异客下一次会移动到下一个字符 $T_{i+1}$ 上。

你需要告诉异客，他会在哪里停下。由于答案会很大，你只需要告诉他对 $10^9+7$ 取模后的结果。

【数据范围】

对于所有测试数据，保证：$1 \le n \le 2 \times 10^{5}$，$1 \le m \le 10^{18}$，$1 \le q \le 2 \times 10^5$，$1 \le s \le 10^{18}$，$0 \le k \le 10^{18}$。

题解

由于题目是循环的字符串，我们不关心它的实际位置，而应该关心它在 $S$ 串上的那个位置，后边称为映射位置。 假设在 A 处移动 $x$ 次可以到达 B 处，在 B 处移动 $y$ 次可以到达 C 处，则在 A 处移动 $x+y$ 次可以到达 C 处。这一类型的题目可以用倍增进行优化，倍增的原理其实就是上面那个，可以自己结合代码理解一下，打 NOIP 应该都会这种倍增吧。
所以我们只要求出在 $S$ 的每个位置一次移动的距离就可以用倍增进行优化再求出答案了。

题目思想还是不难的，实现上有一些分类讨论和特判有一点麻烦，这里重点说一下。 首先是要特判 $S$ 全为 $0$（因为处理时考虑这玩意有点麻烦），这个输出 $s+k$ 就 ok 了，记得这个也要取模，同机房老哥就这样少了 5pts。

然后是计算一次能走多远，不妨让它先走 $m$ 步，在回过来退几步到最近的 $1$ 处，设在 $x$ 处（这是映射到 $S$ 后的位置）要退 $f(x)$ 步，这个可以这样求出来：$f(x) (2 \leq x \leq n) = \begin{cases} 0 & s_x =1 \\ f(x-1)-1 & s_x = 0 \end{cases}$ 特别的，对于 $f(1)$ 若 $s_x \neq 1$ 则可以倒序扫描 $S$ 找到第一个 $1$。

因为答案要对 $10^9+7$ 取模，为了防止其它问题，移动距离我用 __int128 存储。

差不多就这样，把这几个问题处理一下这道题就结束了。 时间复杂度$\mathcal{O}(n\log{n})$

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lll __int128
#define pb push_back
#define fi first
#define se second
#define mp make_pair
const int MAXN=200010,mod=1e9+7;
int a[MAXN],w[MAXN];
ll n,m,s,k,g,q;
lll t[64][MAXN];
void init(){
    if (!a[1]){
        for (int i=n;i>1;i--){
            if (a[i]){
                w[1]=n-i+1;
                break;
            }
        }
    }
    for (int i=2;i<=n;i++) {
       w[i]=a[i]?0:w[i-1]+1;
    }
    for (int i=1;i<=n;i++){
        t[0][i]=max(1ll,m-w[(i+m-1)%n+1]);
    }
    for (int i=1;i<=63;i++){
        for (int j=1;j<=n;j++){
            t[i][j]=t[i-1][j]+t[i-1][(j+t[i-1][j]-1)%n+1];
        }
    }
    return;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin>>n>>m>>q;
    bool tp=1;
    for (int i=1;i<=n;i++){
        char c;cin>>c;
        a[i]=c-'0';
        if (a[i]) tp=0;
    }
    init();
    while (q--){
        cin>>s>>k;
        if (tp){
            cout<<(s+k)%mod<<'\n';
            continue;
        }
        lll ans=s%mod;
        g=log2(k);
        s=(s-1)%n+1;
        for (int i=g;i>=0;i--){
            if (k>=(1ll<<i)){
                k-=(1ll<<i);
                ans=(ans+t[i][s])%mod;
                s=(s+t[i][s]-1)%n+1;
            }
        }
        cout<<(ll)ans<<'\n';
    }
    return 0;
}