题解 P5181 【[COCI 2009] GENIJALAC】

· · 题解

思路不难想，对于每一个在没有剪掉的列上的数，只需判断它移多少次就可以回到原位，然后答案就是每一个合法的列移动次数的最大公倍数。题目中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;
}