自动搬运

查看原文

来自洛谷，原作者为

	sukimo Too lazy to write the description

搬运于2025-08-24 22:07:58，当前版本为作者最后更新于2020-09-12 22:14:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路不难想，对于每一个在没有剪掉的列上的数，只需判断它移多少次就可以回到原位，然后答案就是每一个合法的列移动次数的最大公倍数。题目中$n$很大，所以用$O(n)$算法来求，根据题目数据性质，我们可以发现$s$数组构成了一个图，且这个图每个点必只有一条入边（某位置转移到它这里，不可能两个位置转移到同一个地方）一条出边（向下一个位置转移），那么最终的图应该与下图类似，是由一些互不干扰的有向环构成的。

这就是说，对于在同一环里的两点，它们的移回次数肯定是相同的，所以在一个环里只需统计一次贡献。这样用标记数组就大大的提升了效率。

最后记得开$long\ long$！

$code:$

#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;
bool mark[500005];int mark_cnt,turn[500005];
int dfs(int x){
	if(mark[x])return 0;mark_cnt++;mark[x]=1;return 1+dfs(turn[x]);
}
ll _ceil(ll x,ll y){return (x+y-1)/y;}//手写向上取整函数 
int main(){
	int n,c,d;ll a,b,cnt;scanf("%d%lld%lld%d%d",&n,&a,&b,&c,&d);
	for(int i=1;i<=n;i++)scanf("%d",&turn[i]);
	for(int i=c+1;i<=n-d;i++){
		if(mark[i])continue;//若它被标记过，则与它所属同一个环的某个数已经贡献过
		ll qck=dfs(i);
		cnt=(i!=c+1?cnt/__gcd(cnt,qck)*qck:qck);//第一个特判 
		if(mark_cnt==n-c-d)break;//找完了提前退出 
	}
	printf("%lld",_ceil(b,cnt)-_ceil(a-1,cnt));
	return 0;
}