백준 10830번 : 행렬 제곱[C#]

1. B가 100,000,000,000 까지 될 수 있어서 제곱을 정직하게 시행하면 시간초과가 날 것이다.

> 분할정복의 거듭제곱을 이용해야하고,

 

2. 행렬을 100,000,000,000번 제곱하는 동안 원소가 굉장히 커진다.

> 마지막에 1000으로 나머지 연산을 한다는 조건을 이용하여 나머지 연산의 분배법칙을 적용할 수 있다.

 

3. 분할정복의 거듭제곱을 행렬에도 적용하고, 연산마다 1000으로 나머지 연산을 시행하여 숫자가 과도하게 커지지 않도록 조절한다.

 

분할정복의 거듭제곱과 나머지연산의 분배법칙은 아래 링크에서 다루고 있다.

https://growup.tistory.com/210

알고리즘 문제 관련 수학 모음

 

 

using System;

class Program
{
    static int P = 1000;

    static int N;

    static void Main()
    {
        string[] input = Console.ReadLine().Split();

        N = int.Parse(input[0]);
        long B = long.Parse(input[1]);

        int[,] mat = new int[N, N];
        int[,] res = new int[N, N];

        for (int r = 0; r < N; r++)
        {
            input = Console.ReadLine().Split();
            for (int c = 0; c < N; c++)
            {
                mat[r,c] = int.Parse(input[c]); // 입력받을 때 1000으로 먼저 나누기
    // B= 1 일 때 나머지 연산을 하지 않고 바로 출력하는데, 원소값이 1000인 경우 나머지 연산을 하지 않으면 틀린다. 이 경우를 대비하기 위해 입력받을 때 한 번 나머지연산을 한다.
            }
            res[r,r] = 1; // 단위행렬로 초기화
        }


        while(B != 0) 
        {
            if(B%2 == 1) res = Multiply(res,mat);
            mat = Multiply(mat,mat);
            B/= 2;
        }


        for (int r = 0; r < N; r++)
        {
            for (int c = 0; c < N; c++)
            {
                Console.Write("{0} ", res[r, c]);
            }
            Console.WriteLine();
        }

    }

    static int[,] Multiply(int[,] mat1, int[,] mat2) // 두 행렬의 곱
    {
        int[,] res = new int[N,N];

        for(int r=0; r<N; r++)
        {
            for(int c=0; c<N; c++)
            {
                int n = 0;
                for(int i=0; i<N; i++)
                {
                    n += (mat1[r,i]*mat2[i,c])%P;
                }
                res[r,c] = n%P;
            }
        }
        
        return res;
    }


}