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

朴素算法

本题的暴力思路是模拟。模拟的一个问题是，在模拟过程中取模会破坏模拟结果的正确性，因此我们要避免取模。

注意到使用 __int128 可以做到完整地存下答案而不会溢出。如果用 __int128 存储答案，我们只需要在输出前做一次取模。这个技巧同样也应用在了之后的第一、二级优化方法中。

直接暴力模拟的复杂度 $O(qkm)$，显然是不够的。

优化

第一级优化

依然使用模拟，考虑用预处理进行优化。通过以下代码，读入 $S$ 时可以直接预处理出 $S$ 的每一个位置前（包括本身）最近的 '1' 的位置：

long long l=-m; //记录前一个 `1` 的位置。
for(int i=0;i<n;i++)
{
    char c;
    cin>>c;
    if(c=='1')S[i]=i,l=i; //当前位置就是 `1`。
    else S[i]=l;
}
if(l!=-m)for(int i=0;i<n&&S[i]==-m;i++)S[i]=l-n; //这一句很重要！可以说就是它为避免分讨创造了可能。

我们直接将预处理结果代替原字符串存储在 S[i] 中。注意，对于处于字符串开头的 '0'，其之前最近的 '1' 位于前一个字符串的末尾，我们需要记录这个 '1'，但是要将它的位置减去 n 以体现相对位置。

特殊地，如果字符串全 '0'，S[i] 会被赋值成 -m。这么做的原因请参考下面计算移动量时的代码进行理解。

得到了预处理数组 S[i] 后，我们可以这么计算在 $T$ 中从 $i$ 位置移动 $1$ 次到达的位置（不需要分讨）：

max(i+m-(i+m)%k+S[(i+m)%k],(long long)(i+1));

在这里，我们找到 $T$ 中 $i+m$ 位置前最近的 '1' 的相对位置，并加上 $i+m$ 前完整的 $S$ 的数目以转换为绝对位置。移动后的下一个位置即为该位置和 $i+1$ 中的较大值（最近的 $1$ 可能在 $i+1$ 之前，我们需要舍去，当然，S[i] 为 $-m$ 时也会舍去）。

请注意此处的 $i$ 下标从 $0$ 开始，而输入中的起点位置是从 $1$ 开始的，输入输出时分别需要加上偏移。

经过优化，当前算法的复杂度为 $O(qk)$，可得 $55$ 分。

第二级优化

如何进一步优化？$O(qk)$ 已经是模拟的极限了，为了更好的复杂度，我们需要舍弃模拟法。

让我们使用一下倍增的思想。依然是预处理，我们在处理出 S[i] 的基础上再处理一个数组 t[i][j]，表示从 $T$ 中 $j$ 位置移动 $2^i$ 步到达的位置。这里的 $j$ 只需要处理到 $n-1$ 即可，之后的位置可以通过相对位置的方法计算。

t[0][j] 的计算是很容易的，我们再第一级优化中就已经提供了单次 $O(1)$，共 $O(n)$ 的计算方法：

for(int j=0;j<n;j++)
{
    int k=(j+m)%n; //减少取模运算。
    t[0][j]=max(j+m-k+S[k],(long long)(j+1));
}

从 t[1][j] 开始，可以通过连续进行两次 t[i-1][j] 移动的方式计算 t[i][j] ：

for(int i=1;i<60;i++)
{
    for(int j=0;j<n;j++)
    {
        int k=t[i-1][j]%n;
        t[i][j]=t[i-1][k]-k+t[i-1][j];
    }
}

一共需要处理到 $i=59$（参考数据：$\log_210^{18}\approx59.79470575$）。

最终位置可以根据倍增数组以 $O(\log n)$ 的复杂度求出：

for(int i=0;k;k>>=1,i++)
{
    if(k&1) //位运算将 k 分解为 2 的幂次
    {
        int tt=s%n;
        s=t[i][tt]+s-tt;
    }
}

分析时间复杂度。预处理 $O(n+n\log k)=O(n\log k)$，求解询问 $O(q\log k)$，总复杂度 $O((n+q)\log k)$，是可以接受的。

再分析空间。倍增法依旧会受取模而影响正确性，为了避免计算过程中的取模，我们可以将 t[i][j] 开成 __int128，需要的最大空间为 $2\times10^5\cdot 60\cdot128~\rm bit=192000000~B=183.10546875~MB$，在内存限制允许的范围内。

做到这里已经足够 AC 本题了。

第三级优化

赛时我是用 __int128 存储答案的，故前面三个思路中我都用到 __int128 来解决求解过程中取模造成的答案正确性问题。

其实在倍增法中 __int128 是完全可以避免的，避免了 __int128 的运算可以一定程度上减小常数。而且，使用 __int128 也有一定的投机取巧成分。

long long 是无法存下完整的答案的，所以我们需要在计算过程中就进行对 $10^9+7$ 的取模。然而我们发现倍增过程中存在模 $n$ 的操作，为了防止 $10^9+7$ 和 $n$ 两个模数发生冲突，我们可以将二者分开处理。

开一个辅助数组 t2[i][j]，与 t[i][j] 同步更新。不同的是，t2[i][j] 模 $n$，而 t[i][j] 模 $10^9+7$。所有需要使用模 $n$ 的结果时都改为使用 t2[i][j] 即可。

代码详见 AC 代码部分。

AC 代码

赛时上由于某个小小的疏忽，这道题只得了 $95$ 分。

赛后经过调试得到的 AC 代码如下（使用 __int128）：

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
int n,q;
long long S[200005];
__int128 t[60][200005];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	long long m;
	cin>>n>>m>>q;
	long long l=-m;
	for(int i=0;i<n;i++)
	{
		char c;
		cin>>c;
		if(c=='1')S[i]=i,l=i;
		else S[i]=l;
	}
	if(l!=-m)for(int i=0;i<n&&S[i]==-m;i++)S[i]=l-n;
	for(int j=0;j<n;j++)
	{
		int k=(j+m)%n;
		t[0][j]=max(j+m-k+S[k],(long long)(j+1));
	}
	for(int i=1;i<60;i++)
	{
		for(int j=0;j<n;j++)
		{
			int k=t[i-1][j]%n;
			t[i][j]=t[i-1][k]-k+t[i-1][j];
		}
	}
	while(q--)
	{
		long long s1,k;
		cin>>s1>>k;
		__int128 s=s1-1;
		for(int i=0;k;k>>=1,i++)
		{
			if(k&1)
			{
				int tt=s%n;
				s=t[i][tt]+s-tt;
			}
		}
		cout<<(long long)((s+1)%mod)<<endl;
	}
}

另附不用 __int128 的代码，常数比使用 __int128 小了一半：

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
int n,q;
long long S[200005];
long long t[60][200005];
long long t2[60][200005];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	long long m;
	cin>>n>>m>>q;
	long long l=-m;
	for(int i=0;i<n;i++)
	{
		char c;
		cin>>c;
		if(c=='1')S[i]=i,l=i;
		else S[i]=l;
	}
	if(l!=-m)for(int i=0;i<n&&S[i]==-m;i++)S[i]=l-n;
	for(int j=0;j<n;j++)
	{
		int k=(j+m)%n;
		t[0][j]=max(j+m-k+S[k],(long long)(j+1));
		t2[0][j]=t[0][j]%n;
		t[0][j]%=mod;
	}
	for(int i=1;i<60;i++)
	{
		for(int j=0;j<n;j++)
		{
			int k=t2[i-1][j];
			t2[i][j]=t2[i-1][k];
			t[i][j]=(t[i-1][k]-k+t[i-1][j])%mod;
		}
	}
	while(q--)
	{
		long long s,k,s2;
		cin>>s>>k;
		s-=1;
		s2=s%n;
		for(int i=0;k;k>>=1,i++)
		{
			if(k&1)
			{
				s=(t[i][s2]+s-s2)%mod;
				s2=t2[i][s2];
			}
		}
		cout<<(s+1)%mod<<endl;
	}
}

标题

思路

解题方法

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

标题

题解 -【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;
}