BOJ 2924 - 천재

문제 링크 : https://www.acmicpc.net/problem/2924

문제 풀이

주어진 수열의 i번째 값을 A[i]라고 하자. 우리는 $C\leq k\leq N-D$ 인 k들에 대해서 모든 A[A[A[A[A[...A[k].]]]]=k가 되는 최소 횟수를 찾아야 한다. 당연히 B번을 돌려보는 것은 문제를 해결할 수 있는 방법이 아니다. 최소 횟수를 m이라고 하면 답은 (B회까지 처음과 같은 형태의 개수 - A-1회 까지 처음과 같은 형태의 개수) 이기 때문에 (b+m-1)/m-(a+m-2)/m의 형태가 된다. 따라서 m을 구하기만 하면 된다. 

각 k에 대해서 다시 k로 돌아오는데 까지 걸리는 횟수를 알게 되면 $C\leq k\leq N-D$ 인 k들에 대해서 그 횟수들을 모두 lcm 취해주면 모든 k가 원상태로 돌아온 문제에서 원하는 조건이 되기까지 걸리는 횟수를 알 수 있게 된다. 

이 문제를 그래프 문제로 바꿔서 해결할 것이다. 1번부터 N번까지 N개의 노드가 있다고 가정하고 A[i]=j 라는 것은 i->j의 간선이 존재한다는 것이다. j는 모두 1번씩 등장하기 때문에 전체 그래프는 사이클들로만 이루어져 있게 된다. 따라서 각 k가 크기 몇짜리의 사이클에 속해있는지만 알면 된다. 이는 간선을 이어주는 것 대신에 union 시켜줌으로써 그룹의 크기를 통해 알 수 있다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
ll par[1010101];
ll siz[1010101];
 
ll fi(ll x){
    if(x==par[x]) return x;
    return par[x]=fi(par[x]);
}
 
void uf(ll a,ll b){
    a=fi(a);
    b=fi(b);
    if(a==b) return ;
 
    par[a]=b;
    siz[b]+=siz[a];
}
 
ll arr[1010101];
 
 
int main(){
    ll i,j,k,l,m,n,a,b,c,d;
    scanf("%lld %lld %lld %lld %lld",&n,&a,&b,&c,&d);
    for(i=1;i<=n;i++){
        scanf("%lld",&arr[i]);
        siz[i]=1;
        par[i]=i;
    }
    for(i=1;i<=n;i++){
        uf(i,arr[i]);
    }
    ll alcd=1;
    for(i=1+c;i<=n-d;i++){
        alcd=alcd*siz[fi(i)]/__gcd(alcd,siz[fi(i)]);
    }
    printf("%lld\n",(b+alcd-1)/alcd-(a+alcd-2)/alcd);
}