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