C11CAL - Tính toán
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<bits/stdc++.h>
using namespace std;
class SumOfPowers {
typedef vector<long long> Row;
typedef vector<Row> Matrix;
static const int MOD = 1e9 + 7;
Matrix multiply(const Matrix &a, const Matrix &b) {
int m = a.size(), n = a[0].size(), p = b[0].size();
Matrix res (m, Row(p, 0));
for(int i = 0; i < m; ++i)
for(int j = 0; j < p; ++j)
for(int k = 0; k < n; ++k)
res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % MOD;
return res;
}
Matrix power(Matrix a, int n) {
Matrix res (a.size(), Row(a.size(), 0));
for(unsigned i = 0; i < res.size(); ++i) res[i][i] = 1;
for(; n > 0; n >>= 1) {
if(n & 1) res = multiply(res, a);
a = multiply(a, a);
}
return res;
}
public:
int value(int n, int k) {
Matrix a (1, Row(k + 2, 0)); a[0][0] = 1;
Matrix p (k + 2, Row(k + 2, 0));
p[0][0] = 1;
for(int j = 1; j <= k; ++j) {
p[0][j] = 1;
for(int i = 1; i <= j; ++i)
p[i][j] = (p[i-1][j-1] + p[i][j-1]) % MOD;
}
for(int i = 0; i <= k; ++i) p[i][k+1] = p[i][k];
p[k+1][k+1] = 1;
return multiply(a, power(p, n)).front().back();
}
};
int main() {
ios::sync_with_stdio(false);
for(int n, k; cin >> n >> k; cout << SumOfPowers().value(n, k) << '\n');
return 0;
}