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;
}

Download