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

为了方便我们从 $0$ 开始下标。

考虑倍增。设 $f(i, j)$ 表示从 $i$ 开始，移动 $2^j$ 次后，实际位置的偏移量。转移：
$$
f(i, j) = f(i,j-1)+f((i+f(i,j-1)) \bmod n, j-1)
$$
考虑 $f(i, 0)$，也就是移动 $1$ 次走的实际步数怎么求。

先令 $g(l, r)$（$0 \le l,r < n$）表示 $[l, r]$ 内最后一个 $1$ 的位置。可以二分+预处理前缀和轻易求解。

分类讨论 $[i+1,i+m]$ 是否跨过至少一次完整的 $S$。

举个例子。$n=4$。那么 $T_{0\sim 3} = T_{4 \sim 7} = T_{8 \sim 11} = \dots = S$。希望求解 $f(2, 0)$。有三种情况：

![](https://cdn.luogu.com.cn/upload/image_hosting/lzwfwgmm.png)

- $i+m < n$（即图中 $\color{red}m=1$）：显然 $f(i,0) = g(i+1, n-1)-i$。毕竟你都没走出第一段。

- $n \le i+m < 2n$（即图中 $\color{blue}m=4$）：也就是先走第一段的一段后缀（具体是 $[i+1,n-1]$），再走第二段的一段前缀（具体是 $[0, m-n+i]$）。先看第二段的前缀中是否存在 $1$，有则 $f(i,0)=n-1-i+g(0,m-n+i)$。否则 $f(i, 0) = g(i+1,n-1)-i$，也就是第一种情况。

- $i+m \ge 2n$（即图中 $\color{green} m=11$）：也就是先走第一段的一段后缀（$[i+1,n-1]$），然后走 $\left\lfloor \dfrac{m-n+1+x}n \right\rfloor$ 个完整段，再走下一段的一段前缀（$[0,(x+m) \bmod n]$）。跟第二种情况类似，先判断最后一段的前缀中是否存在 $1$，再判最后一个完整段中是否存在 $1$，再判倒数第二个完整段中是否存在 $1$，以此类推，最后判第一段的前缀中是否存在 $1$。

注意到每个完整段都是相同的，都是 $S$。所以我们只需要判最后一个完整段即可。~~式子有一坨懒得打了。~~

然后就差不多做完了。细节还是很多的。推荐一道相似的答辩题 AT_abc346_f，也有这么一坨分类讨论。

一个细节：

- $f(i, j)$ 最大是 $km$，会炸 `long long`。有两种方法：一种是直接 `__int128`，但带很多取模常数很大；一种是观察到我们只需要知道 $f(i, j) \bmod n$ 和 $f(i,j) \bmod P$（$P = 10^9 + 7$），所以开两个数组分别维护这两个模数的值。这样甚至 `long long` 都不用开，而且取模可以用减法优化掉，常数很小。

代码：

```cpp
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;

const int N = 2e5 + 10, P = 1e9 + 7;

int n, q;
ll m;
char s[N];
int sum[N];
int st_n[N][63], st_P[N][63];

int mod_n(int a) {
	return a < n ? a : a - n;
}

int mod_P(int a) {
	return a < P ? a : a - P;
}

int calc(const int l, const int r) {
	// 查询 [l, r] 中最后一个 1 的位置。
	int lo = l, hi = r, res = -1;
	while (lo <= hi) {
		const int mid = lo + hi >> 1;
		if (sum[r] - sum[mid - 1]) {
			res = mid;
			lo = mid + 1;
		} else {
			hi = mid - 1;
		}
	}
	return res;
}

ll get(const int x) {
	// 从 x 开始移动一次，位置的偏移量
	if (x + m < n) {
		int res = calc(x + 1, x + m);
		return res == -1 ? 1 : res - x;
	}

if (x + m >= 2 * n) {
		// 至少经过完整一段
		int res = calc(0, (x + m) % n);
		if (~res) {
			if ((x + m) % n == n - 1) {
				return n - 1 - x + (m - n + 1 + x) / n * n;
			}
			return n - 1 - x + (m - n + 1 + x) / n * n + res + 1;
		}
		res = calc(0, n - 1);
		if (~res) {
			return n - 1 - x + ((m - n + 1 + x) / n - 1) * n + res + 1;
		}
		return 1;
	}
  
	// 一段前缀和一段后缀
	int res = calc(0, m - n + x);
	if (~res) {
		return res + 1 + n - 1 - x;
	}
	res = calc(x + 1, n - 1);
	if (~res) {
		return res - x;
	}
	return 1;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> n >> m >> q;

for (int i = 0; i < n; ++ i ) {
		cin >> s[i];
		sum[i] = sum[i - 1] + s[i] - '0';
	}

for (int i = 0; i < n; ++ i ) {
		ll t = get(i); 
		st_n[i][0] = t % n;
		st_P[i][0] = t % P;
	}

for (int j = 1; j < 63; ++ j ) {
		for (int i = 0; i < n; ++ i ) {
			st_n[i][j] = mod_n(st_n[i][j - 1] + st_n[mod_n(i + st_n[i][j - 1])][j - 1]);
			st_P[i][j] = mod_P(st_P[i][j - 1] + st_P[mod_n(i + st_n[i][j - 1])][j - 1]);
		}
	}
  
  while (q -- ) {
		ll s, k;
		cin >> s >> k;
		s -- ;
		int res_n = 0, res_P = 0;
		
		for (int i = 62; ~i; -- i ) {
			if (k >= (1ll << i)) {
				k -= 1ll << i;
				int ans_n = st_n[(s + res_n) % n][i];
				int ans_P = st_P[(s + res_n) % n][i];
				res_n = mod_n(res_n + ans_n);
				res_P = mod_P(res_P + ans_P);
			}
		}
  	
		cout << (s + res_P + 1) % P << '\n';
	}
	
	return 0;
}
```

正在渲染内容...