백준(BOJ) 13328 Message Passing *

# 수학

우선 수가 크기 때문에 dp로도 안풀린다.

-> logn으로 해결해야한다.

수학 행렬을 사용하면 된다.

이 문제를 풀기 전에 피보나치수3을 푸는것을 추천한다.

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

피보나치 수은 이전의 2개를 더한다면

이번 문제에서는 이전의 d개의 수를 더해주면 된다.

여기서 기존의 d=2 기존의 피보나치의 수와 같은 행렬의 제곱으로 해결할 수 있고

d>2의 경우, 다음과 같이 해결이 된다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define MAX 1005
#define INF 987654321
#define MOD 31991
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

int d,t;

struct st
{
    int m[55][55] = {};
    st operator*(st a) const
    {
        st ret;
        for (int i = 0; i < d; i++)
            for (int j = 0; j < d; j++)
                for (int k = 0; k < d; k++)
                    ret.m[i][j] = (ret.m[i][j] + m[i][k] * a.m[k][j]) % MOD;
        return ret;
    }
}ans,ori,b;

int main()
{
    scanf("%d%d",&d,&t);
    for(int i=0;i<d;i++)
    {
        ans.m[i][i]=ori.m[0][i]=1;
        if(0<i)
            ori.m[i][i-1]=1;
    }
    while(t>0)
    {
        if(t%2==1)
            ans=ans*ori;
        ori=ori*ori;
        t/=2;
    }
    printf("%d",ans.m[0][0]);
    return 0;
}