自动搬运

查看原文

来自洛谷，原作者为

	zhaoyp 曲终人散，悄然离场

搬运于2025-08-24 22:24:45，当前版本为作者最后更新于2021-07-23 21:33:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

对于 $35 pts$ 的数据

由于 $k \le 10^5$，直接按题意模拟即可。

对于所有的数据

由于 $1 \le k \le 10^{18}$，直接模拟显然是行不通的，考虑优化。

如果将第 $u$ 个人批评第 $v$ 个人的定义为一个状态的话，因为一共有 $n$ 个人，每个人可以对其他 $n - 1$ 个人进行批评 ，那么 $k$ 次批评最多的状态数为： $n \times (n - 1) = 500 \times 499 = 249500$ 。

因为在确定上一次批评的批评者和被批评者时，下一次批评的批评者和被批评者是确定的。换句话说，对于已知的现有状态，有唯一确定的下一状态。如果将状态视为节点，批评的过程视为边的话，则每个节点出度均为 $1$。

以样例 $2$ 为例：

3 7
0 3 2
3 0 3
2 1 0

通过模拟我们不难发现第 $1$ 次和第 $4$ 次批评都是第 $1$ 个人批评第 $2$ 个人，可见在 $k$ 次批评中有许多状态会被重复访问。即该图中存在环，大量批评的过程在此环中重复进行，浪费了大量时间。我们只需找出此环，在进入到环中任意一节点时，将剩余批评次数对环的长度进行求余，再模拟即可，这样就省去了无数次在环中“绕圈”的过程。

code

下面给出递归实现：

#include<bits/stdc++.h>
int n,a[505][505],vis[505][505];
long long m;
void input()
{
	scanf("%d%lld",&n,&m);
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n;j++)
			scanf("%d",&a[i][j]);
}
void dfs(int x,int y,long long k)
{
	if(vis[x][y])
		m = (m - k) % (k - vis[x][y]) + k;
	if(k == m)
	{
		printf("%d",x);
		exit(0);
	}
	vis[x][y] = k;
	dfs(y,a[y][x],k + 1);
}
int main()
{
	input();
	dfs(1,2,1);
	return 0;
}