【題解】Codeforces 1117D. Magic Gems

#include <iostream>
#include <cstring>
using namespace std;
 
long long n, m, mod = 1e9+7;
struct mat{
    long long a[100][100];
    mat(){
        memset(a, 0, sizeof(a));
    }
    mat operator * (const mat & b)const{
        mat ret;
        for (int i = 0; i < m; i++){
            for (int j = 0; j < m; j++){
                for (int k = 0; k < m; k++){
                    ret.a[i][j] = (ret.a[i][j] + a[i][k] * b.a[k][j]) % mod;
                }
            }
        }
        return ret;
    }
};
 
int main() {
    while (cin >> n >> m){
        mat in;
        for (int i = 0; i < m; i++){
            in.a[i][0] = 1;
        }
        mat we;
        for (int i = 1; i < m; i++){
            we.a[i-1][i] = 1;
        }
        we.a[m-1][0] = 1;
        we.a[m-1][m-1] = 1;
        while (n){
            if (n & 1){
                in = we * in;
            }
            we = we * we;
            n >>= 1;
        }
        cout << in.a[0][0] << "\n";
    }
}