CS Academy - Substring restrictions

* CS Academy - Substring restrictions

[분류 - DSU/ Dynamic programming]

  심플한 문제에 비해 굉장히 난이도가 높은 문제입니다. 처음엔 레이지 세그트리로 덤볐다가, 시간초과와 메모리 초과를 동시에 받아버린..

  

[해설]

  쿼리 len x y를 로 표기하고 'x부터 x+len-1까지 각각을 y부터 y+len-1까지 각각을 같게 보겠다'라는 의미로 보겠습니다.

  가장 간단하게 브루트포스로 먼저 생각해봅시다. 이를 구현하기 위해서는 단순히 하나의 반복문으로 해결할 수 있습니다. 이 때 '같아야 한다'를 DSU에서의 union(또는 merge)의 의미로 받아주시면 되겠습니다. 당연히 범위가 10^11까지 올라가므로 O(NM)으로는 시간이 만족할 수 없습니다. 이제 우리는 이 구조와 동치 관계를 갖는 구조를 설계해야 하죠.

1. 쿼리 분할

  에 대해 생각해봅시다. 1 <= t < len에 대해, 는 아래처럼 표현될 수 있습니다.

 ===  그리고 

  간단하게 for문 하나를 for문 두 개로 나눴다고 생각합시다. 그러면 위 표현식이 맞음을 직관적으로 알 수 있어요.

  여기서 t를 결정해봅시다. 위 쿼리 분할은 임의의 t에 대해서 점화식 구조를 가지고 있습니다. 따라서 쿼리를 분할하며 len 값을 줄여나갈 때 짜임새 있게 줄여나가야 점화식 구조를 활용할 수 있습니다. 여기서 t가 2의 승수일 때가 가장 짜임새 있는 구조를 갖게 됩니다.

* t=2의 승수

  len=2^k일 때 생각해봅시다. 다른 값은 나중에 일반화하며 설명하겠습니다.

  1 <= t < len에 대해 t의 가장 큰 값은 2^(k-1)이 됩니다. 따라서 =는 아래처럼 표현할 수 있습니다.

   ===  그리고 

2. len != 2^k

  len이 2^k꼴이 아닐 때 생각해봅시다. 다시, k는 2^k < len을 만족하는 k중 가장 큰 값을 가지는 것을 상기하며, 와 동치인 관계를 찾아야 합니다.

  를 2^k로 표현해봅시다. 처음은 , 그 다음은 , 또 , ... ,로 를 표현할 수 있습니다.

  의 의미를 다시 생각해보면 "x부터 x+2^k-1까지 각각을 y부터 y+2^k-1까지 각각을 같게 보겠다"입니다. 그러면 과 는 겹치는 부분이 정확히 2^k-1개가 겹칩니다. 이 겹쳐지는 부분을 모두 제외하면 결국 시작과 끝인 와 밖에 남지 않습니다. 중간에 있는 들은 모두 중첩이 되기 때문이죠. 중첩되는 이유는? k가 2^k < len을 만족하는 k중 가장 큰 값을 가지게끔 해서입니다.

3. 사이값 계산

  점화식 구조에 의해 이제 반씩 계산해 나가줍시다. 

  를 와 로 분리할 수 있기에 모든 지점에 대해서 쭉 순회하며 합쳐주시면(union) 됩니다. 이 과정은 라는 쿼리가 들어왔을 때 이미 x와 y를 합쳤기 때문에 x를 y의 부모로 두든, y를 x의 부모를 두든 상관이 없습니다.

[구현]

  요약하자면

  1. 모든 쿼리 에 대해 2^k <= len을 만족하는 k값 중 최대값을 찾습니다.

  2.  그리고 로 쿼리를 분할합니다.

  3. 1.에서 구한 k를 '차원'으로 두고 x와 y를 union하고, x+len-2^k와 y+len-2^k를 union합니다.

  4. k를 내림차순으로 0보다 클 때까지 진행하며, i는 0부터 N-1인 문자열 인덱스로 둡니다.

     u = find(i)이면 u+2^(k-1)과 i+2^(k-1)를 union합니다.

#include<iostream>
#include<set>
using namespace std;
const int MOD = 1e9 + 7, MAX_N = 1e6, MAX_K = 20;
int n = MAX_N;
int find(int *p, int u){ return u == p[u] ? u : p[u] = find(p, p[u]); }
void merge(int *p, int u, int v){
    u = find(p, u), v = find(p, v);
    if(u == v) return;
    p[u] = v;
}
int main() {
	int N, M, ans = 1, len, x, y, p[MAX_K][MAX_N], i, j, k, max_k = 0, used[MAX_N] = {};
	scanf("%d%d",&N, &M);
	for(i=0;i<MAX_K;i++) for(j=0;j<N;j++)
		p[i][j] = j;
	while(M--){
		scanf("%d%d%d",&len, &x,&y);
		for(k=0;(1 << k) <= len; k++);
		k--, x--, y--;
		merge(p[k], x, y);
		merge(p[k], x + len - (1 << k), y + len - (1 << k));
		max_k = max(max_k, k);
	}
	for(j=max_k;j;--j) for(i=0;i<N;i++) {
		x = find(p[j], i);
		merge(p[j - 1], i, x);
		merge(p[j - 1], i + (1 << (j-1)), x + (1 << (j-1)));
	}
	for(i=0;i<N;i++) {
		x = find(p[0], i);
		if(!used[x]) {
			used[x] = 1;
			ans = ans * 26LL % MOD;
		}
	}
	printf("%d",ans);
	return 0;
}