13328번: Message Passing

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

dp[i]: 시각이 i일 때 전화 수
i) i < 0
dp[i] = 0
ii) i = 0
dp[i] = 1
iii) i > 0
dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-d]

답은 dp[t]이다. 행렬을 이용하면 $O(\lg t)$ 횟수의 행렬 곱으로 답을 구할 수 있다.

#include<cstdio>
#define mod 31991
int d, t;
struct st {
    int m[50][50] = {};
    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;
    }
}u, r;
int main() {
    scanf("%d%d", &d, &t);
    for (int i = 0; i < d; i++) r.m[i][i] = u.m[0][i] = 1;
    for (int i = 1; i < d; i++) u.m[i][i - 1] = 1;
    for (; t; t >>= 1, u = u*u) if (t & 1) r = r*u;
    printf("%d", r.m[0][0]);
    return 0;
}