백준 29705번: 문자열 만들기

https://www.acmicpc.net/problem/29705

29705번: 문자열 만들기

---

Notation이 좀 난해한 문제였습니다.

 

그러나 25962번과 아이디어가 비슷하다는 걸 캐치하면, 풀이의 앞 부분은 쉽게 해결됩니다.

---

우선 자연수 $N$에 대해 $g(x)=N$인 $x$의 개수를 $A_{N}$으로 놓으면

$$A_{N+9} = |S_{1}| \times A_{N+8} + |S_{2}| \times A_{N+7} + \cdots + |S_{8}| \times A_{N+1} + |S_{9}| \times A_{N}$$

이고, $N$이 작은 경우

$$A_{N} = \sum_{i=1}^{N} \left ( |S_{i}| \times A_{N-i} \right ) \;\; (N \leq 9,\; A_{0} = 1)$$

입니다.

 

이런 점화식에서 $A_{N}$ 하나의 값을 구하는 시간 복잡도는 $O(dN)$부터 $O(d^{3} \log N)$, $O(d^{2} \log N)$, $O(d \log d \log N)$ 까지 다양합니다. $(d=9)$

 

그러나, 이 문제는 구간 합을 구하길 원하므로 $A_{a}$부터 $A_{b}$까지의 값을 모두 구하느냐, 혹은 더 세련된 방법을 쓰느냐로 접근 방식을 나누게 됩니다.

---

전자의 경우, FFT + Kitamasa를 쓰더라도 $b-a$의 상한이 $5 \times 10^{6}$이므로, 구간에 속한 모든 값을 하나하나 구할 수는 없습니다. (다시 말해, $O(d \log d \times (b-a))$는 시간 초과입니다.)

 

하지만, $A_{a}$부터 $A_{a+8}$까지의 값을 구하면, 이후 $A_{a+9}$부터 $A_{b}$까지의 값은 $O(9(b-a))$로 구할 수 있게 됩니다.

 

한편 이 9개의 값을 구하는 것은 어떻게 구하더라도 큰 상관은 없겠지만, 저는 아래 식을 썼습니다.

$$\begin{bmatrix} A_{a+8} \\ A_{a+7} \\ A_{a+6} \\ \vdots \\ A_{a+1} \\ A_{a} \end{bmatrix} = \begin{bmatrix} |S_{1}| & |S_{2}| & |S_{3}| & \cdots & |S_{8}| & |S_{9}| \\ 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 1 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \ddots & 0 & 0 \\ 0 & 0 & 0 & \cdots & 1 & 0 \end{bmatrix}^{a} \begin{bmatrix} A_{8} \\ A_{7} \\ A_{6} \\ \vdots \\ A_{1} \\ A_{0} \end{bmatrix}$$

 

이 방법의 시간복잡도는 결국 $O(d^{3}\log a + d(b-a))$ 인데, 캐시 덕분인지 생각보다는 빠른 실행시간이 나오는 걸로 보입니다.

---

후자는 약간의 식 변형을 필요로 하겠습니다.

행렬 $M$의 $i$행 $j$열을 $M_{ij}$로 표기한다면, (저는 0-index를 쓰겠습니다)

$$A_{N} = \left ( \begin{bmatrix} |S_{1}| & |S_{2}| & |S_{3}| & \cdots & |S_{8}| & |S_{9}| \\ 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 1 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \ddots & 0 & 0 \\ 0 & 0 & 0 & \cdots & 1 & 0 \end{bmatrix}^{N} \begin{bmatrix} A_{8} \\ A_{7} \\ A_{6} \\ \vdots \\ A_{1} \\ A_{0} \end{bmatrix} \right )_{80}$$

이므로, $B_{N} = \sum_{i=0}^{N} A_{N}$ 이면,

$$B_{N} = \sum_{i=0}^{N} \left ( \begin{bmatrix} |S_{1}| & |S_{2}| & |S_{3}| & \cdots & |S_{8}| & |S_{9}| \\ 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 1 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \ddots & 0 & 0 \\ 0 & 0 & 0 & \cdots & 1 & 0 \end{bmatrix}^{i} \begin{bmatrix} A_{8} \\ A_{7} \\ A_{6} \\ \vdots \\ A_{1} \\ A_{0} \end{bmatrix} \right )_{80}$$

$$= \left ( \left ( \sum_{i=0}^{N} \begin{bmatrix} |S_{1}| & |S_{2}| & |S_{3}| & \cdots & |S_{8}| & |S_{9}| \\ 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 1 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \ddots & 0 & 0 \\ 0 & 0 & 0 & \cdots & 1 & 0 \end{bmatrix}^{i} \right ) \begin{bmatrix} A_{8} \\ A_{7} \\ A_{6} \\ \vdots \\ A_{1} \\ A_{0} \end{bmatrix} \right )_{80}$$

으로 식이 정리가 되며, $d \times d$ 행렬의 거듭제곱의 합 또한 $O(d^{3} \log N)$에 계산됩니다.

 

즉, 이 방법의 시간 복잡도는 $O(d^{3}(\log a + \log b))$가 됩니다.

 

참고로, 어떤 좋은 행렬에 대해서는 geometric progression처럼 취급하여 거듭제곱의 합을 구할 수 있습니다만,

 

역행렬이 보장되는지도 문제이고, 구현량도 많아지는 것 같습니다. 이 글과 이 글을 참고해볼 수는 있을 것 같습니다.

 

일단 아래는 제 코드입니다.

#include <stdio.h>
#include <string.h>
#define mod 1000000007

typedef struct {
    unsigned long long array[9][9];
} Matrix;

Matrix I;

Matrix matrix_multiply_modular (Matrix A, Matrix B);
Matrix matrix_power_modular (Matrix A, long long P);
Matrix matrix_power_sum_modular (Matrix A, long long P);

int main() {
    
    for (int i = 0; i < 9; i++) I.array[i][i] = 1;
    
    long long a, b;
    scanf("%lld %lld", &a, &b);

    char string[10][51] = {{}};
    long long len[10] = {};
    for (int i = 1; i <= 9; i++) {
        scanf("%s", string[i]);
        len[i] = strlen(string[i]);
    }
    
    long long s[10] = {1};
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= i; j++) {
            s[i] += s[i - j] * len[j];
        }
        s[i] %= mod;
    }
    
    Matrix simple = {{{}}};
    for (int i = 0; i < 9; i++) {
        simple.array[i][0] = s[i];
    }
    
    Matrix base = {{{}}};
    for (int i = 0; i < 9; i++) {
        base.array[8][i] = len[9 - i];
    }
    for (int i = 0; i + 1 < 9; i++) {
        base.array[i][i + 1] = 1;
    }
    
    Matrix temp;
    
    temp = matrix_multiply_modular(matrix_power_sum_modular(base, b), simple);
    long long ans_b = temp.array[0][0];
    
    temp = matrix_multiply_modular(matrix_power_sum_modular(base, a - 1), simple);
    long long ans_am1 = temp.array[0][0];
    
    long long answer = (ans_b + mod - ans_am1) % mod;
    printf("%lld", answer);
    
    return 0;
}

Matrix matrix_addition_modular (Matrix A, Matrix B) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            A.array[i][j] = (A.array[i][j] + B.array[i][j]) % mod;
        }
    }
    return A;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B) {
    Matrix result = {{{}}};
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            for (int k = 0; k < 9; k++) {
                result.array[i][j] += A.array[i][k] * B.array[k][j];
            }
            result.array[i][j] %= mod;
        }
    }
    return result;
}

Matrix matrix_power_modular (Matrix A, long long P) {
    Matrix result = I;
    while(P) {
        if (P % 2) {
            result = matrix_multiply_modular(result, A);
        }
        A = matrix_multiply_modular(A, A);
        P /= 2;
    }
    return result;
}

Matrix matrix_power_sum_modular (Matrix A, long long P) {
    // A^0 + A^1 + A^2 + ... + A^P
	if (P <= 0) {
		return I;
	}
	if (P % 2) {
		return matrix_multiply_modular(matrix_power_sum_modular(A, P / 2),
                                       matrix_addition_modular(matrix_power_modular(A, (P + 1) / 2), I));
	}
	else {
		return matrix_addition_modular(matrix_power_modular(A, P / 2),
		                               matrix_multiply_modular(matrix_power_sum_modular(A, P / 2 - 1),
		                                                       matrix_addition_modular(I,
		                                                                               matrix_power_modular(A, P / 2 + 1))));
	}
}

(C11, 8ms, 1384KB, 제출번호 67070258)

---

생각 이상으로 제 matrix_power_sum이 비효율적이었는지, 28ms부터 8ms까지 널뛰는 것 같습니다.

 

12987번을 다시 확인해봐야할 것 같습니다...