BOJ 15502 - K-균등 문자열

BOJ 15502 - K-균등 문자열

$l_i \sim r_i$ 에서 $k_i$ 만큼 차이나는 수들은 모두 같아야 한다.

$1 \to N$ 까지의 모든 수들중 이러한 제약이 걸린 것들을 DSU로 묶어준다.

이것의 의미는 DSU로 묶인 수들은 하나가 결정되면 나머지 하나도 모두 그걸로 같게 결정된다는 의미이다.

DSU에서 트리의 개수를 $K$라고 하면 정답은 $2^K$가 된다.

struct st {
   int l, r, k;
};
struct DSU {
   vector<int> p;
   DSU(int n) : p(n, -1) {}
   int gp(int n) {
      if (p[n] < 0) return n;
      return p[n] = gp(p[n]);
   }
   void merge(int a, int b, int to_b = 0) {
      a = gp(a), b = gp(b);
      if (a == b) return;
      if (!to_b && size(a) > size(b)) swap(a, b);
      p[b] += p[a];
      p[a] = b;
   }
   bool is_merged(int a, int b) { return gp(a) == gp(b); }
   int size(int n) { return -p[gp(n)]; }
};
void solve() {
   int n, m;
   cin >> n >> m;
   vector<st> a(m);
   for (int i = 0; i < m; i++) cin >> a[i].l >> a[i].r >> a[i].k, a[i].l--, a[i].r--;
   vi fixed(n);
   sort(all(a), [&](auto &a, auto &b) {
      return a.l < b.l;
   });
   DSU dsu(n);
   for (int i = 0; i < m; i++) {
      for (int j = 0; j < a[i].k; j++) {
         for (int x = a[i].l + j + a[i].k; x <= a[i].r; x += a[i].k) {
            dsu.merge(x, x - a[i].k);
         }
      }
   }
   int c = 0;
   for (int i = 0; i < n; i++) if (dsu.gp(i) == i) c++;
   int ans = 1;
   for (int i = 0; i < c; i++) ans = md(ans * 2);
   cout << ans;
}