Codeforces Round #138 (Div. 1) C : Partial Sums
問題概要
数列Aに対して、f(A)[i] = sum_{j<=i} A[j]とする。f^k(A)を求める問題。数列の長さ<2000, K<10^9。
解法
ひっくり返して考えると上三角Toeplitz行列なので、巡回行列と同じように行列を圧縮して持つことができる。よって積がO(N^2)で計算できるので後はバイナリ法で累乗を計算すればよい。
acceptされたコード
#include <cstdio> #include <vector> #include <algorithm> using namespace std; typedef long long int64; const int64 MOD = int64( 1e9 + 7 ); struct UpperTriangularToeplitzMatrix : vector<int64> { UpperTriangularToeplitzMatrix(int size, int64 value = 0): vector<int64>(size, value) {} int64 get(int i, int j) const { return (i <= j ? operator[](j - i) : 0); } }; UpperTriangularToeplitzMatrix getIdentity(int size){ UpperTriangularToeplitzMatrix ret(size, 0); ret[0] = 1; return ret; } const UpperTriangularToeplitzMatrix operator +(const UpperTriangularToeplitzMatrix& lhs, const UpperTriangularToeplitzMatrix& rhs) { const int n = lhs.size(); UpperTriangularToeplitzMatrix ret(n, 0); for (int i = 0; i < n; ++i) { ret[i] = (lhs[i] + rhs[i]) % MOD; } return ret; } const UpperTriangularToeplitzMatrix operator -(const UpperTriangularToeplitzMatrix& lhs, const UpperTriangularToeplitzMatrix& rhs) { const int n = lhs.size(); UpperTriangularToeplitzMatrix ret(n, 0); for (int i = 0; i < n; ++i) { ret[i] = (lhs[i] - rhs[i] + MOD) % MOD; } return ret; } const UpperTriangularToeplitzMatrix operator *(const UpperTriangularToeplitzMatrix& lhs, const UpperTriangularToeplitzMatrix& rhs) { const int n = lhs.size(); UpperTriangularToeplitzMatrix ret(n, 0); for (int k = 0; k < n; ++k) { for (int j = 0; j < n; ++j) { ret[j] = (ret[j] + lhs.get(0, k) * rhs.get(k, j)) % MOD; } } return ret; } const UpperTriangularToeplitzMatrix calcPow(const UpperTriangularToeplitzMatrix &x, const int64 k) { const int n = x.size(); UpperTriangularToeplitzMatrix ret = getIdentity(n), base = x; for (int64 e = k; e ; e >>= 1) { if (e&1) { ret = ret * base; } base = base * base; } return ret; } const vector<int64> operator *(const UpperTriangularToeplitzMatrix &lhs, const vector<int64> &rhs) { const int n = lhs.size(); vector<int64> ret(n, 0); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { ret[i] = (ret[i] + lhs.get(i, j) * rhs[j]) % MOD; } } return ret; } const int MAX_N = 2000; int N, K; int64 as[MAX_N]; void init() { scanf("%d%d", &N, &K); for (int i = 0; i < N; ++i) { scanf("%lld", as + i); } } void solve() { UpperTriangularToeplitzMatrix matrix(N, 1); reverse(as, as + N); vector<int64> ans = calcPow(matrix, K) * vector<int64>(as, as + N); reverse(ans.begin(), ans.end()); for (int i = 0; i < N; ++i) { printf("%lld%c", ans[i], i==N-1 ? '\n' : ' '); } } int main() { init(); solve(); return 0; }