CF1056G Take Metro 题解

*2900 的题，评到黑题是因为 std 做法要用可持久化平衡树，然而有一种更简洁的做法。

注意到 \(t\) 很大，然后每一步只和 \(t\bmod n\) 的大小有关系，因此你想先求出 \(t=n\) 时每一个点最后会走到哪些点，然后倍增处理，至于剩下的不能整除 \(n\) 的部分暴力跑即可（下面认为 \(t\) 已经暴力预处理掉了不能整除 \(n\) 的部分）。

然后你想推性质推出这个走到的点，结果你发现你推不出来，没有轨迹可循。

然后你想打个暴力输出来看一眼，然后发现似乎最后每个点能够走到的点构成的集合并不大，不过最大的也会有 \(\dfrac{n}{5}\) 左右，但是一般情况下 \(n=10^5\) 时大概有 \(4000\) 个左右。

但是这样还是没法处理，由于最后的点高度重合，于是你怀疑所有点最后会走到一个环里面，于是你决定处理出每个点走到哪个点之后环长大小。

然后你发现环长特别小，自己手造时最大值也才 10。

然后你猜测这个环很小，完全可以从起点直接预处理出这个环，然后在这个环上遍历，因为 \(t\) 每经过环长 \(\times n\) 的时间就会回到这个点，于是可以让 \(t\) 对这个值取模，然后 \(t\) 就很小了，又可以暴力跑了，当然你会发现起点不一定在环内，要先拉到环里面再跑，同时记得将 \(t\) 开成 long long。

然后你过了。

实际上最大环长某位评论区老哥胡出来期望是 \(O(\sqrt{n})\)，但是不会证，而 \(O(n\sqrt{n})\) 照样能过。

写的全新风格的题解？我以前题解基本上看不到“你”这个字（

Code：

/*
========= Plozia =========
	Author:Plozia
	Problem:CF1056G Take Metro
	Date:2022/11/9
========= Plozia =========
*/

#include <bits/stdc++.h>
typedef long long LL;

const int MAXN = 1e5 + 5;
int n, m, s, Next[MAXN];
LL t;

int Solve(int x, int p) { return ((x + p) > n) ? (x + p - n) : (x + p); }

void Brute(int s, LL t)
{
	for (LL i = t; i >= 1; --i)
	{
		s = Solve(s, (s <= m) ? (i % n) : (n - (i % n)));
	}
	printf("%d\n", s);
}

int main()
{
	std::cin >> n >> m >> s >> t; int x = 0;
	for (int i = t % n; i >= 1; --i, --t) { s = Solve(s, (s <= m) ? i : (n - i)); }
	if (t == 0) { printf("%d\n", s); return 0; }
	for (x = s; !Next[x]; x = Next[x])
	{
		int tmp = x;
		for (int i = n; i >= 1; --i) tmp = Solve(tmp, (tmp <= m) ? i : (n - i));
		Next[x] = tmp;
	}
	int cnt = 0; for (int pz = s; pz != x; pz = Next[pz]) ++cnt;
	if (t <= 1ll * cnt * n) { Brute(s, t); return 0; }
	t -= 1ll * cnt * n; cnt = 1; s = x; for (int pz = Next[x]; pz != x; pz = Next[pz]) ++cnt;
	t %= 1ll * cnt * n; Brute(s, t); return 0;
}