백준 24415번: 편지

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

24415번: 편지

---

이 문제가 생각나기도 합니다.

---

기본적인 아이디어는 $C$개의 규칙을 모두 합친 것을 $\lfloor \frac{K}{C} \rfloor$ 번 반복하고, $1$번째 규칙부터 $K \;\; \% \;\; C$ 번째 규칙까지 마저 진행한다는 것입니다.

 

각각의 규칙을 행렬로 나타내는 아이디어는 기본적으로 identity matrix에서 특정 원소만 수정한다고 생각하면 됩니다.

 

Latex로 보여드리자니 행렬의 사이즈가 좀 커지는 것 같아서, 코드를 참고해주시면 감사하겠습니다.

 

그리고 $O(C)$개의 규칙을 어떻게 merge하느냐인데, $i$번째 규칙이 $S \;\; a \;\; b$인 경우 $a$번째 row와 $b$번째 row를 swap하고, $A \;\; a \;\; b$인 경우 $a$행의 원소를 적절히 수정해주면 됩니다.

 

왜냐하면, 이 문제의 규칙을 행렬로 나타낸 것이 $I$와 매우 닮아서 그렇다고 말할 수 있겠습니다. (당연히, 아무 규칙도 없을 때는 $I$입니다.)

---

그 다음으로 생각해야하는 부분은 이 문제에서 알파벳에 대해 Z 다음이 A라고 정의한 부분입니다. 이로 인해 모듈로를 26으로 설정할 근거가 생깁니다.

 

이제 시간복잡도를 계산해보면, $C$개의 규칙을 merge할 때 모든 규칙이 swap인 경우 $O(NC)$가 소요됩니다. 따라서, 전체 시간 복잡도는 $O(NC + N^{3} \log K)$입니다.

 

물론 17401번처럼 생각하면 $O(N^{2}C + N^{3} \log K)$입니다만, 이렇게 하면 시간을 초과해버립니다.

 

아래는 제 코드입니다.

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

typedef struct {
    unsigned int array[101][101];
} Matrix;

Matrix I;

Matrix matrix_multiply_modular (Matrix A, Matrix B, int size);
Matrix matrix_power_modular (Matrix A, int size, long long P);

int main() {
    
    int N, C;
    long long K;
    scanf("%d %d %lld", &N, &C, &K);
    
    char letter[101] = {};
    scanf("%s", letter);
    
    Matrix original = {{{}}};
    for (int i = 0; i < N; i++) {
        original.array[i][0] = letter[i] - 'A';
    }
    original.array[N][0] = 1;
    
    int size = N + 1;
    for (int i = 0; i < size; i++) {
        I.array[i][i] = 1;
    }
    
    int rem = K % C;
    Matrix rule_remainder = I;
    Matrix rule_around = I;
    
    unsigned int temp[101];
    for (int i = 1; i <= C; i++) {
        char Type;
        int a, b;
        scanf(" %c %d %d", &Type, &a, &b);
        
        if (Type == 'S') {
            memcpy(temp, &rule_around.array[a][0], size * sizeof(int));
            memcpy(&rule_around.array[a][0], &rule_around.array[b][0], size * sizeof(int));
            memcpy(&rule_around.array[b][0], temp, size * sizeof(int));
            
            if (i <= rem) {
                memcpy(temp, &rule_remainder.array[a][0], size * sizeof(int));
                memcpy(&rule_remainder.array[a][0], &rule_remainder.array[b][0], size * sizeof(int));
                memcpy(&rule_remainder.array[b][0], temp, size * sizeof(int));
            }
        }
        else {
            rule_around.array[a][N] = (rule_around.array[a][N] + b) % mod;
            
            if (i <= rem) {
                rule_remainder.array[a][N] = (rule_remainder.array[a][N] + b) % mod;
            }
        }
    }
    
    Matrix Total_Change = matrix_multiply_modular(rule_remainder, matrix_power_modular(rule_around, size, K / C), size);
    Total_Change = matrix_multiply_modular(Total_Change, original, size);
    for (int i = 0; i < N; i++) {
        printf("%c", Total_Change.array[i][0] + 'A');
    }
    return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B, int size) {
    Matrix result = {{{}}};
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            for (int k = 0; k < size; 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, int size, long long P) {
    Matrix result = {{{}}};
    for (int i = 0; i < size; i++) {
        result.array[i][i] = 1;
    }
    while (P) {
        if (P % 2) {
            result = matrix_multiply_modular(result, A, size);
        }
        A = matrix_multiply_modular(A, A, size);
        P /= 2;
    }
    return result;
}

(C11, 56ms, 1512KB, 제출번호 67088919)

 

시간복잡도를 계산 안 했을 땐 $C$의 크기 때문에 겁을 먹었었는데 다시 보니 별 거 없었습니다.