【題解】CSES 1096 Throwing Dice

#include <iostream>
using namespace std;
 
long long n, a[6][6], ans[6], mod = 1e9+7;
 
int main() {
    cin >> n;
    for (int i = 0; i < 5; i++){
        a[i][i+1] = 1;
    }
    for (int i = 0; i < 6; i++){
        a[5][i] = 1;
    }
    ans[5] = 1;
    while (n){
        if (n & 1){
            long long tmp[6] = {};
            for (int i = 0; i < 6; i++){
                for (int j = 0; j < 6; j++){
                    tmp[i] += a[i][j]*ans[j];
                    tmp[i] %= mod;
                }
            }
            for (int i = 0; i < 6; i++){
                ans[i] = tmp[i];
            }
        }
        long long tmp[6][6] = {};
        for (int i = 0; i < 6; i++){
            for (int j = 0; j < 6; j++){
                for (int k = 0; k < 6; k++){
                    tmp[i][j] += a[i][k]*a[k][j];
                    tmp[i][j] %= mod;
                }
            }
        }
        for (int i = 0; i < 6; i++){
            for (int j = 0; j < 6; j++){
                a[i][j] = tmp[i][j];
            }
        }
        n >>= 1;
    }
    cout << ans[5] << "\n";
}