【題目敘述】http://codeforces.com/problemset/problem/1117/D
【解題想法】矩陣快速冪,DP
#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";
}
}