세상의 변화에 대해 관심이 많은 이들의 Tech Blog search

BOJ 09012(괄호) 문제 풀이

|

참조

분류 URL
문제 괄호
이 글에서 설명하는 코드 09012_괄호

개요

시간복잡도: $ O(TC \cdot L) $

공간복잡도: $ O(L) $

  • TC는 테스트 케이스의 수, L은 문자열의 길이이다.

문제 풀이

괄호 짝 맞추기는 스택 문제의 단골손님이다.
이 문제의 핵심 아이디어는 다음과 같다.

  • 문자열을 하나씩 읽는다.
    • 여는 괄호 ( 가 나오면 스택에 집어넣는다.
    • 닫는 괄호 ) 가 나오면 괄호 하나를 빼낸다.
      • 이때 스택이 비어 있으면 잘못된 것이다. NO를 출력한다.
  • 문자열을 다 읽고 나서 스택이 비어 있어야만 제대로 된 Parenthesis String이다. YES를 출력한다.
    • 스택에 뭔가 들어 있으면 NO를 출력한다. 이 부분이 실수가 가장 많이 나오는 부분이다.
  • 각 테스트 케이스마다 스택을 clear시켜줘야 한다. 안 그러면 wrong answer를 받을 것이다.

구현

이 문제에는 적용 가능한 트릭이 몇 가지 있다. 코딩을 간단하게 만들 수 있다.

  • 이 문제는 스택에 집어넣는 것이 오직 여는 괄호 ( 하나 뿐이다. 그럼 굳이 스택을 쓸 것도 없이, 쌓인 여는 괄호의 수를 세어 줄 변수 n 하나만 있으면 된다.
  • 각 문자마다 검사할 때, 닫는 괄호 ) 가 나오면 일단 n을 감소시킨다. 그리고 n이 0보다 작아지면, 바로 중단한다.
    • 그러면 마지막에서 n이 0인지만 보면 YES / NO 를 판별할 수 있다.
#include <string>
#include <iostream>

using namespace std;

int main_09012() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);    cin.tie(NULL);

    int TC;

    cin >> TC;
    while (TC--) {
        int n = 0;
        string str;
        cin >> str;
        for (auto s : str) {
            if (s == '(')
                ++n;
            else 
                --n;
            if (n < 0)break;
        }
        cout << (n ? "NO" : "YES") << '\n';
    }
    return 0;
}

주의: 이 코드를 그대로 복붙하여 채점 사이트에 제출하면 틀린다. 그대로 제출하지 말라는 뜻이다. 무언가를 바꿔 주어야 한다.

Comment  Read more

greeksharifa's Library

|

sharifa_header.h

코드

필자가 만든 라이브러리…라고 하기는 좀 그렇고, 그냥 헤더 파일이랑 #define 약간을 모아 놓은 헤더 파일이다.
필자의 코드에서 처음 보는 토큰들이 좀 있을 텐데, 잘 모르겠다면 위의 링크를 참조하면 된다.

예를 들면, lllong long이다.

bit_library.h

코드

비트 관련 사용자 정의 함수를 모아 놓은 헤더 파일이다.
bit 연산을 안다면 코드를 보고 이해할 수 있으므로 따로 설명하지는 않겠다.

conversion_library.h

코드

어떤 데이터 타입 변수를 다른 데이터 타입 변수로 바꾸는 함수들을 모아 놓았다.
예를 들어 string_to_vi 함수는 “1236”과 같은 string을 vector<int>로 변환한다.

Comment  Read more

고속 푸리에 변환(Fast Fourier Theorem, FFT). 큰 수의 곱셈

|

참조

분류 URL
문제 큰 수 곱셈
응용 문제 koosaga BOJ FFT 문제집
참조 라이브러리 sharifa_header.h, bit_library.h
이 글에서 설명하는 라이브러리 fft.h

개요

시간복잡도: $ O(N log N) $

공간복잡도: $ O(N) $

  • N은 두 수열의 길이의 max값이다.
  • FFT는 convolution을 빠르게 해 주는 것이지만, PS에서는 거의 대부분 곱셈을 빠르게 하기 위해 쓰인다.

이 글에서는 FFT(고속 푸리에 변환)을 설명한다.
이론적인 부분에 대한 자세한 설명은 topology-blog에 잘 되어 있으므로 생략한다.


알고리즘

큰 수의 곱셈을 수행할 때 FFT의 개략적인 설명은 다음과 같이 적어 두었다.

  1. 각 수열을 먼저 reverse시킨다. $ O(N) $
  2. 각 수열에 푸리에 변환을 적용한다. $ O(N log N) $
  3. 푸리에 변환을 적용하면 convolution을 단순 곱셈으로 변환시킬 수 있으므로, 2의 결과물을 element-wise 곱셈을 시킨다. $ O(N) $
  4. 3의 결과물을 푸리에 역변환을 시킨다. $ O(N log N) $
  5. 1에서 reverse를 시켰으므로, 다시 reverse를 시켜준다. $ O(N) $

FFT의 핵심 부분은 2~4번 부분이다. 1번과 5번은 우리가 수를 쓸 때 앞부분에 큰 자리 수를 적기 때문에 필요하다.

구현

다음과 같다. FFT 구현과 출력 함수만 정의되어 있으므로, 따로 설명하진 않겠다.

다만 주의할 점이 하나 있는데, 출력 함수에서 곱하는 두 수가 0인 경우 예외 처리를 해주어야 한다.

/*
fft 함수는 http://topology-blog.tistory.com/6 블로그를 참조한 것입니다.
*/

#pragma once

#include "sharifa_header.h"
#include "bit_library.h"

typedef complex<double> base;

void fft(vector<base> &a, bool inv) {
    int n = (int)a.size();
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        while (!((j ^= bit) & bit)) bit >>= 1;
        if (i < j) swap(a[i], a[j]);
    }
    for (int i = 1; i < n; i <<= 1) {
        double x = (inv ? 1 : -1) * M_PI / i;
        base w = { cos(x), sin(x) };
        for (int j = 0; j < n; j += i << 1) {
            base th(1);
            for (int k = 0; k < i; k++) {
                base tmp = a[i + j + k] * th;
                a[i + j + k] = a[j + k] - tmp;
                a[j + k] += tmp;
                th *= w;
            }
        }
    }
    if (inv) {
        for (int i = 0; i < n; i++) a[i] /= n;
    }
}

vector<int> multiply(vector<int> &A, vector<int> &B) {
    vector<base> a(A.begin(), A.end());
    vector<base> b(B.begin(), B.end());
    int n = power_of_2_ge_than(max(a.size(), b.size())) * 2;

    a.resize(n);	b.resize(n);
    fft(a, false);	fft(b, false);

    for (int i = 0; i < n; i++)
        a[i] *= b[i];
    fft(a, true);

    vector<int> ret(n);
    for (int i = 0; i < n; i++)
        ret[i] = (int)round(a[i].real());
    return ret;
}

BOJ 13277(큰 수 곱셈) 문제 풀이

문제: BOJ 13277(큰 수 곱셈)

풀이: BOJ 13277(큰 수 곱셈) 문제 풀이

Comment  Read more

BOJ 06549(히스토그램에서 가장 큰 직사각형) 문제 풀이

|

참조

분류 URL
문제 히스토그램에서 가장 큰 직사각형
이 글에서 설명하는 코드 06549_히스토그램에서 가장 큰 직사각형

개요

시간복잡도: $ O(TC \cdot N) $

공간복잡도: $ O(N) $

  • N은 직사각형의 수, TC는 테스트 케이스의 수이다. 즉 사실상 $ O(N) $이다.

이 글에서는 히스토그램에서 가장 큰 직사각형의 가장 빠른 풀이인 스택을 활용한 풀이를 설명한다.
이 문제는 BOJ 사이트 맨 아래에 적혀 있는 대로 세그먼트 트리($O(N log N)$), 분할 정복($O(N log N)$) 등으로도 풀 수 있다.


문제 풀이

개인적으로 스택 활용 문제 중 가장 멋있는 문제라고 생각…

이 문제는 처음 봤을 때는 스택이라는 것을 떠올리기가 굉장히 까다롭다. 하지만 가장 멋있는 풀이 방법이니 꼭 익혀두도록 하자.

우선 $O(N^2)$ 풀이부터 생각해 보자.

$O(N^2)$ 풀이: 그냥 풀기

사실 이 풀이는 별 것 없다. N개의 직사각형이 있으니, [0, N) 구간이라고 생각하고, 모든 구간의 넓이를 다 구해보는 것이다. 그리고 최댓값을 찾는다.

  1. [0, 1) 부터 [0, 2), [0, 3), …, [0, N) 구간을 검사한다. 각 구간 최댓값을 유지하면서 차례로 검사한다.
  2. [1, 2) 부터 [1, 3), [1, 4), …, [1, N) 구간을 검사한다. 각 구간 최댓값을 유지하면서 차례로 검사한다.
  3. [N-1, N) 구간을 검사한다. 각 구간 최댓값을 유지하면서 차례로 검사한다(하나뿐이지만).
  4. 이 중 최댓값을 찾는다.

당연히 $O(N^2)$ 풀이는 시간 초과를 얻는다. 이를 $O(N)$으로 줄이기 위해서는, 한 칸씩 검사할 때마다 $O(N)$에 해당하는 구간을 검사해야 한다.
그리고 이를 가능하게 해 주는 것이 스택이다.

$O(N)$ 풀이: 스택

이 풀이를 어떻게 생각해냈을까라는 생각은 잠시 접어두고, 우선 풀이를 보자.

  1. 스택을 하나 생성하고, 답(ans)은 0으로 초기화해 둔다.
  2. 0번째 직사각형을 처리한다. (첫 번째 직사각형이지만, 0으로 시작하는 것이 편하다)
    1. 0번째는 우선 스택에 집어넣어 둔다. 이 때 pair<int, int>를 사용하여, (위치, 직사각형의 높이)를 같이 저장한다.
  3. i번째 직사각형을 처리한다.
    1. 이때 스택에는 몇 개인지는 모르지만 (위치, 직사각형의 높이) 쌍이 몇 개 들어 있을 것이다.
    2. 스택의 top element의 높이와 i번째 직사각형의 높이를 비교한다. top element를 (top_index, top_height), i번째 직사각형을 (i_index, i_height)라고 하자.
    3. top_height <= i_height이면(혹은 3.iv.b에서 다 제거해버려서 스택이 비었으면) (최소 위치, 직사각형의 높이) 쌍을 스택에 집어넣고 (i+1)번째 직사각형으로 넘어간다.
      1. top_height == i_height이면 집어넣지 않아도 상관없지만, 코드가 복잡해지므로 그냥 한 번에 처리한다.
      2. 최소 높이란, min(i_height, 마지막으로 제거한 top_height)를 의미한다. 제거한 적이 없으면 그냥 i_height이다.
    4. top_height > i_height이면, 다음을 수행한다.
      1. (i_index - top_index) * top_height와 ans의 max값을 ans에 넣는다.
      2. top element를 제거한다. 이때 top_height는 임시저장한다.
    5. 모든 직사각형을 처리했으면, 남은 스택의 top element에 대해서 iv의 동작을 반복한다.
      1. 이때 i_index 대신 n을 사용한다.

이것이 알고리즘의 전부이다.
BOJ의 예시(2 1 4 5 1 3 3)를 적용해 보자. 아래 그림은 BOJ에서 가져온 것이다.

Histogram

  1. 스택을 하나 생성하고, ans 변수는 0으로 초기화해 둔다.
  2. 0번째 직사각형을 처리한다.
    1. (0,2)를 저장한다.
  3. 1번째 직사각형을 처리한다.
    1. (0,2)가 스택에 있다.
    2. (0,2)와 (1,1)을 비교한다. 1번째 직사각형이 top element보다 더 작다.
      1. (i_index - top_index) * top_height = (1-0)*2 = 2를 ans에 저장한다.
        • 이것은 0번째 직사각형만을 사용하여 잘라낸 직사각형을 의미한다. 너비 1, 높이 2짜리 직사각형이다.
      2. (0,2)를 스택에서 제거한다. 이때 최소 위치는 0이 된다.
    3. 스택이 비었으므로 (0,1)을 집어넣고((1,1)이 아니다!) 다음으로 넘어간다.
      • 이것의 의미는 다음과 같다. 위치는 0, 높이는 1을 집어넣었다. 이는 1번째 직사각형을 포함하는(높이 1 이상) 잘라낸 직사각형의 왼쪽 끝은 0이 된다는 뜻이다.
      • 그림을 보면 이해가 될 것이다. 0,1번째 직사각형 모두에서 잘라낼 때 최대 높이는 1이다.
  4. 2번째 직사각형을 처리한다.
    1. (0,1)이 스택이 있다.
    2. (0,1)과 (2,4)를 비교한다. 2번째 직사각형이 top element보다 더 크다.
    3. (2,4)를 스택에 넣고 다음으로 넘어간다.
  5. 3번째 직사각형을 처리한다.
    1. (0,1)과 (2,4)가 스택에 있다.
    2. (2,4)와 (3,5)를 비교한다. (3,5)를 스택에 넣고 다음으로 넘어간다.
  6. 4번째 직사각형을 처리한다.
    1. (0,1), (2,4), (3,5)가 스택에 있다.
    2. (3,5)와 (4,1)을 비교한다. 4번째 직사각형이 더 작다.
      1. (4-3)*5 = 5를 ans에 저장한다.
        • 3번째 직사각형만을 사용하여 잘라낸 것을 의미한다.
      2. (3,5)를 스택에서 제거한다. 최소 위치를 3으로 업데이트한다.
    3. (2,4)와 (4,1)을 비교한다. 이번에도 4번째 직사각형이 더 작다.
      1. (4-2)4 = 8을 ans에 저장한다(이것이 이 예시의 정답이다*).
        • 2,3번째 직사각형을 사용하여 잘라낸 것을 의미한다.
      2. (2,4)를 스택에서 제거한다. 최소 위치를 2로 업데이트한다.
    4. (0,1)과 (4,1)을 비교한다. 높이가 같으므로 (2,1)((4,1)이 아니다!)을 스택에 집어넣고(넣지 않아도 된다) 다음으로 넘어간다.
  7. 5번째 직사각형을 처리한다.
    1. (0,1), (2,1)이 스택에 있다.
    2. (5,3)은 (2,1)보다 높이가 높기 때문에 스택에 그대로 집어넣고 다음으로 넘어간다.
  8. 6번째 직사각형을 처리한다.
    1. (0,1), (2,1), (5,3)이 스택에 있다.
    2. (6,3)은 (5,3)과 높이가 같기 때문에 스택에 그대로 집어넣고 다음으로 넘어간다.
  9. 이제 모든 직사각형을 처리했으니, 스택을 비워가면서 처리를 하면 된다.
    1. (0,1), (2,1), (5,3), (6,3)이 스택에 있다.
    2. (6,3): (7-6)*3 = 3은 ans보다 작다. 6번째 직사각형만을 사용하여 잘라낸 것(너비 1, 높이 3)이다.
    3. (5,3): (7-5)*3 = 6은 ans보다 작다. 5,6번째 직사각형을 사용하여 잘라낸 것(너비 2, 높이 3)이다.
    4. (2,1): (7-2)*1 = 5은 ans보다 작다. 4,5,6번째 직사각형을 사용하여 잘라낸 것(너비 5, 높이 1)이다.
    5. (0,1): (7-0)*1 = 7은 ans보다 작다. 0~6번째 직사각형을 모두 사용하여 잘라낸 것(너비 7, 높이 1)이다.

같은 방법으로
1,2,3,2,1(정답은 1~3번째 직사각형을 사용한 6)과
3,2,1,2,3(정답은 0~4번째 직사각형을 모두 사용한 5)
에 대해서도 생각해 보라.

이 알고리즘에 왜 동작하는지를 살펴보면 다음과 같다.

  1. 스택에는 항상 위치와 직사각형의 높이 모두 오름차순으로 정렬되어 쌓여 있다. top element가 더 높으면 항상 제거하기 때문에 이렇게 된다.
  2. i번째 직사각형을 처리할 때, 1에 의해 놓치는 잘라낸 직사각형이 없게 된다.
    1. 즉, (i-1)번째 직사각형이 잘라낸 직사각형의 오른쪽 끝이 되는 모든 경우를 처리하는 것이다.
  3. 최소 높이를 사용하는 이유는, 3,2,1,2,3과 같은 경우를 처리하기 위함이다.
    1. 만약에 3번째 직사각형을 처리할 때 (2,1)로 그대로 집어넣어 버리면, 0~4번째 직사각형을 모두 포함한 넓이 5짜리 직사각형을 놓치게 된다.
    2. 1에 의해 i번째 직사각형보다 낮은 top element를 처음 만나기 전까지는 모두 top element가 i번째 직사각형보다 높으므로, 높이 걱정을 할 필요가 없어진다.

이해가 안 된다면, 예시를 몇 개 더 생각해 보면서 해야 한다. 추천하는 예시는 1,2,5,2,2,1,6이다.

다음은 자주 하는 실수를 정리한 것이다.

  1. 마지막에 스택을 비우는 작업을 안 하는 경우. 이것은 마지막 직사각형이 잘라낸 직사각형의 오른쪽 끝이 되는 경우를 놓친 것이다.
  2. 높이 10억 * 너비 10만은 int의 범위를 한참 넘는다. ans는 long long으로 선언할 것.

구현

이 문제에 적용 가능한 트릭이 몇 가지 있다.

  1. 높이가 같은 경우 스택에 넣어도 되고 안 넣어도 된다. 직관을 위해서라면 넣지 말고, 코딩의 편의성을 위해서라면 따로 처리할 필요 없다.
  2. 스택을 비우는 작업을 따로 처리하는 대신, 높이 -1짜리 가상의 n번째 직사각형을 생각하자. 그러면 모든 직사각형은 이 n번째 직사각형보다 높기 때문에 스택에서 모두 제거되게 된다.

최소 위치left이다. 설명이 복잡한 것 치고는 간결한 코드이지 않은가?

#include "../library/sharifa_header.h"

int main_06549() {
    int n;
    while (true) {
        scanf("%d", &n);
        if (!n)break;
        stack<pair<int,int> > st;
        ll ans = 0;
        for (int i_index = 0; i_index <= n; i_index++) {
            int i_height;
            if (i_index < n)
                scanf("%d", &i_height);
            else
                i_height = -1;
            int left = i_index;
            // top_index: st.top().first, top_height: st.top().second
            while (!st.empty() && st.top().second > i_height) {
                ans = max(ans, ((ll)i_index - st.top().first)*st.top().second);
                left = st.top().first;
                st.pop();
            }
            st.push(make_pair(left, i_height));
        }
        printf("%lld\n", ans);
    }
    return 0;
}

주의: 이 코드를 그대로 복붙하여 채점 사이트에 제출하면 당연히 틀린다. 못 믿겠다면, 저런 헤더 파일이 채점 사이트에 있을 것이라 생각하는가?

Comment  Read more

행렬의 N 거듭제곱 빠르게 구하기

|

참조

분류 URL
문제 행렬 제곱
응용 문제 스포일러 1
참조 라이브러리 sharifa_header.h, bit_library.h
이 글에서 설명하는 라이브러리 matrix.h

개요

시간복잡도: $ O(M^3 log N) $

공간복잡도: $ O(M^2) $

  • M은 행렬의 크기, N은 거듭제곱할 수를 나타낸다. 물론 행렬은 정사각행렬이다.

이 글에서는 행렬의 N 거듭제곱을 빠르게 구하는 방법을 설명한다. 사실 행렬의 N승은 정수의 N 거듭제곱 빠르게 구하기을 구하는 것과 근본적으로 동일하다.
다만 단순 정수의 곱이 아닌 행렬곱을 사용할 뿐이다.


알고리즘

먼저 예를 하나 들어보자. 행렬 $A$의 11승을 구하고 싶다고 하자. 어떻게 계산하는 것이 빠르겠는가?

단순무식한 방법을 적자면, $A^2$부터 구하면 된다. 그리고 $A^3$을 구한다. … 마지막으로 $A^{11}$을 구한다.
그러면 계산량은? 행렬곱 10번이다.

나쁘지 않은데? 라고 생각한다면, N이 크면 당연히 시간 초과임을 생각하라. N이 10억쯤 한다면? 10억 번을 1초 안에 계산할 수 있겠는가?
문제처럼 N(문제에서는 B이다.)이 $10^{11}$이나 한다면?

당연히 이 방법으로는 어림도 없다. 그럼 조금 더 좋은 방법을 생각해야 한다.

이제 $A^{11} = A \cdot A \cdot A \cdot A \cdot A \cdot A \cdot A \cdot A \cdot A \cdot A \cdot A$를 조금 다르게 써 보자.

[A^{11} = (A^5)^2 \cdot A]

만약에 여러분이, $A^5$를 알고 있다고 하자. 그러면 계산을 몇 번이나 해야 할까?
행렬곱은 딱 두 번 뿐이다.

조금 전 단순무식하게 구할 때를 떠올려보자. $A^5$로부터 $A^{11}$을 구하는 것은 행렬곱 연산이 6번이나 필요했다.
그러나 지금은 단 두 번만에 해결이 된다.

이제 $A^5$를 구하는 방법을 생각해보자. 다음을 생각할 수 있을 것이다.

[A^5 = (A^2)^2 \cdot A]

[A^2 = (A)^2]

그러면 이것을 어떻게 코드로 옮길 것인가?
고려할 것이 몇 가지 있다. 하나씩 살펴보자.

  • A의 N승을 위의 방법으로 구할 때 반드시 고려해야 하는 부분은, 현재 구하고자 하는 N이 짝수인지 홀수인지이다.
    • 만약 홀수라면, 다음과 같다. $ A^{2k+1} = (A^k)^2 \cdot A$이다.
    • 만약 짝수라면, 조금 더 간단하다. $ A^{2k} = (A^k)^2 $이다.
  • $A^N$을 구하기 전에, 먼저 2진수로 나타내 본다. N=11인 경우, N=$1011_2$이다.
  • $A^{11}$을 종이에 쓰고 천천히 생각해보라. 다음 두 가지 중 맞는 것은 무엇인가? N=$1011_2$이다.
    • 가장 끝자리 비트(LSB)부터 고려하여 위의 거듭제곱 알고리즘을 따른다.
    • 가장 앞자리 비트(MSB)부터 고려하여 위의 거듭제곱 알고리즘을 따른다.
    • 답은 MSB부터 고려하는 것이다. N=11로 놓고 종이에 써보면, MSB를 고려하는 것은 $A^{11}$을 구하지만, LSB를 고려하는 것은 $A^{13}$을 구하게 될 것이다.
    • 이것이 바로 matrix.h에서 bit_reverse 함수를 사용하는 이유이다.
    • 한 가지 더 주의할 점은, 비트 반전만 해서는 안된다. 100이 001로 바뀌어 그냥 1이 되기 때문이다. 따라서 자리수를 기억해 두어야 한다.

이제 $A^{11}$는 다음과 같은 순서로 구하면 된다는 것을 알 수 있을 것이다. 11=$1011_2$임을 기억하라.
물론 $A^0 = 1$이다.

이진수
1 $ (A^0)^2 \cdot A = A^1 $
0 $ (A^1)^2 = A^2 $
1 $ (A^2)^2 \cdot A = A^5 $
1 $ (A^5)^2 \cdot A = A^{11} $

조금 더 복잡한 예를 들어보겠다. 46=$101110_2$이다.

이진수
1 $ (A^0)^2 \cdot A = A^1 $
0 $ (A^1)^2 = A^2 $
1 $ (A^2)^2 \cdot A = A^5 $
1 $ (A^5)^2 \cdot A = A^{11} $
1 $ (A^{11})^2 \cdot A = A^{23} $
0 $ (A^{23})^2 = A^{46} $

이진수로 나타냈을 때 해당 자리가 1이면 제곱한 후 A를 추가로 곱하고, 0이면 그냥 제곱만 하면 된다.

행렬의 거듭제곱은 아주 복잡하지는 않다. 헷갈린다면 정수의 N 거듭제곱 빠르게 구하기을 참조하라.

구현

거듭제곱이 구현된 행렬 클래스는 다음과 같다. 필자의 편의를 위해, re_define.h#define을 활용한 많은 단축 선언들을 사용했다.

#include "sharifa_header.h"
#include "bit_library.h"

vector<vector<int> > mat_mul(vector<vector<int> > matrix_A, vector<vector<int> > matrix_B, int mod) {
    int m = matrix_A.size();
    vector<vector<int> > ret(m, vector<int>(m));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < m; k++) {
              ret[i][j] += ((ll)matrix_A[i][k] * matrix_B[k][j]) % mod;
              ret[i][j] %= mod;
            }
        }
    }
    return ret;

}

vector<vector<int> > matrix_power_N(vector<vector<int> > matrix, int N, int mod, bool print) {
    int m = matrix.size(), len = binary_len(N);
    vector<vector<int> > original = matrix;
    vector<vector<int> > ret = vector<vector<int> >(m, vector<int>(m));
    for (int i = 0; i < m; i++)
        ret[i][i] = 1;
    
	N = bit_reverse(N);
    while (len--) {
        ret = mat_mul(ret, ret, mod);
        if (N & 1) {
            ret = mat_mul(ret, original, mod);
        }
        N >>= 1;
    }
    if (print) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++)
                printf("%d ", ret[i][j]);
            puts("");
        }
    }
    return ret;
}

문제 풀이

사용법은 어렵지 않다. 행렬을 2차원 벡터로 만든다.
그리고 행렬을 N승을 취한 후, print 인자를 true로 주어 matrix_power_N 함수를 호출하면 문제는 풀린다.

#include "../library/matrix.h"

#define mod 1000

int main_10830() {
    int m, N;
    scanf("%d%d", &m, &N);

    vector<vector<int> > original = vector<vector<int> >(m, vector<int>(m));
    for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &original[i][j]);

    matrix_power_N(original, N, mod, true);
    return 0;
}

주의: 이 코드를 그대로 복붙하여 채점 사이트에 제출하면 당연히 틀린다. 못 믿겠다면, 저런 헤더 파일이 채점 사이트에 있을 것이라 생각하는가?

Comment  Read more