BOJ 25614 - 자리 바꾸기

BOJ 25614 - 자리 바꾸기

기본적인 순열 싸이클 분할 문제이지만 $M \le 10^{200,000}$ 이란 제한이 발목을 붙잡는다.

$10^N$ 을 특정 수로 나눈 나머지를 $O(N)$ 에 구할 수 있다고 할 때, 크기 $M$ 을 가지는 순열 그룹에서의 서로 다른 순열 싸이클 분할의 개수는 $O(\sqrt M)$ 라는 것을 파악하여 특정 길이에 대한 나머지 값을 DP로 처리하면 $O(M\sqrt{N})$ 에 문제를 해결할 수 있다.

구현은 큰 수의 나머지 연산에 대해 c++ 이라면 bigint 같은 구현체나 파이썬에서 하면 수월하다.

void solve() {  
   int n;  
   bigint m;  
   cin >> n >> m;  
  
   vi a(n);  
   fv(a);  
   for (int &i: a)i--;  
  
   vi vis(n);  
  
   vi ans(n);  
   vi dp(n, -1);  
   for (int i = 0; i < n; i++) {  
      if (vis[i]) continue;  
      vi group;  
      int j = i;  
      do {  
         vis[j] = 1;  
         group.pb(j);  
         j = a[j];  
      } while (!vis[j]);  
  
      if (sz(group) == 0) {  
         ans[group[0]] = group[0];  
      } else {  
         int offset = ~dp[sz(group)] ? dp[sz(group)] : bigint(m) % sz(group);  
         dp[sz(group)] = offset;  
         for (int j = 0; j < sz(group); j++) {  
            ans[group[j]] = group[(j + offset) % sz(group)];  
         }  
      }  
   }  
   for (int i: ans) cout << i + 1 << ' ';  
}