题解 P5181 【[COCI 2009] GENIJALAC】

sukimo

2020-09-12 22:14:39

Solution

思路不难想,对于每一个在没有剪掉的列上的数,只需判断它移多少次就可以回到原位,然后答案就是**每一个合法的列移动次数的最大公倍数**。题目中$n$很大,所以用$O(n)$算法来求,根据题目数据性质,我们可以发现$s$数组构成了一个图,且这个图每个点必只有一条入边(某位置转移到它这里,不可能两个位置转移到同一个地方)一条出边(向下一个位置转移),那么最终的图应该与下图类似,是由一些互不干扰的有向环构成的。 ![p](https://cdn.luogu.com.cn/upload/image_hosting/v24q5zzn.png?x-oss-process=image/resize,m_lfit,h_170,w_225) 这就是说,对于在同一环里的两点,它们的移回次数肯定是相同的,所以在一个环里只需统计一次贡献。这样用标记数组就大大的提升了效率。 最后记得开$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; } ```