BOJ 15502 - K-균등 문자열
에서 만큼 차이나는 수들은 모두 같아야 한다.
까지의 모든 수들중 이러한 제약이 걸린 것들을 DSU로 묶어준다.
이것의 의미는 DSU로 묶인 수들은 하나가 결정되면 나머지 하나도 모두 그걸로 같게 결정된다는 의미이다.
DSU에서 트리의 개수를 라고 하면 정답은 가 된다.
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;
}
Comments