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