「SPOJ SEQ」 Recursive Sequence

Description

定义数列 (a) 的第 (i) 项 (a_i) 的公式为：

(egin{cases} a_i = b_i & i le k \ a_i = sumlimits_{t=1}^k a_{i-t} imes c_{t} & i > k end{cases})

现给定 (k,b={b_1, b_2, cdots ,b_k},c={c_1, c_2, cdots ,c_k},n) ，求 (a_n mod 10^9) 的值。

Hint

(1le kle 10)

(1le nle 10^9)

(0le b_i, c_ile 10^9)

Solution

不错的矩阵优化递推 (k) 项递推式的板子。没有常数项更加简单。

首先，对于 (n le k) 的情况，直接输出 (b_n) 的值。

对于 (n > k) 的情况，需要使用矩阵加速。

[egin{bmatrix} a_i \ a_{i-1} \ vdots \ a_{i-k} end{bmatrix} = egin{bmatrix} c_1 & cdots & c_{k-1} & c_k \ 1 & cdots & 0 & 0 \ vdots & ddots & vdots & vdots \ 0 & cdots & 1 & 0 end{bmatrix} imes egin{bmatrix} a_{i-1} \ a_{i-2} \ vdots \ a_{i-k-1} end{bmatrix} ]

这种题的套路差不多就是：最上面一排系数，下面斜着放 1。

怎么理解这个式子呢？

新矩阵的 (a_i) 项是由旧矩阵中所有元素分别乘上系数的和而来，而新矩阵的其他元素可以直接由旧矩阵的元素那里拿过来，并且下移一位。

这样时间复杂度是 (O(k^3 log n)) 的。

Code

/*
 * Author : _Wallace_
 * Source : https://www.cnblogs.com/-Wallace-/
 * Problem : SPOJ SEQ Recursive Sequence
 */
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int mod = 1e9;
typedef long long LL;
typedef vector<LL> vec;
typedef vector<vec> mat;

inline mat operator * (mat a,mat b) {
	mat x(a.size(), vec(b[0].size(), 0));
	for (register int i = 0; i < a.size(); i++)
		for (register int j = 0; j < b[0].size(); j++)
			for (register int k = 0; k < b.size(); k++)
				(x[i][j] += a[i][k] * b[k][j]) %= mod;
	return x;
}

inline mat matI(int n) {
	mat x(n, vec(n, 0));
	for (register int i = 0; i < n; i++)
		x[i][i] = 1;
	return x;
}

mat fastpow(mat base, int k) {
	if (!k) return matI(base.size());
	mat x = fastpow(base, k >> 1);
	if (k & 1) return (x * x) * base;
	else return x * x;
}

void solve() {
	int n, k;
	cin >> k;
	mat b(k, vec(1, 0)), c(k, vec(1, 0));
	for (register int i = 0; i < k; i++)
		cin >> b[i][0];
	for (register int i = 0; i < k; i++)
		cin >> c[i][0];
	cin >> n;
	
	if (n <= k) cout << b[n - 1][0] << endl;
	else {
		mat base(k, vec(k, 0));
		for (register int i = 0; i < k; i++)
			base[0][i] = c[i][0];
		for (register int i = 1; i < k; i++)
			base[i][i - 1] = 1;
		reverse(b.begin(), b.end());
		b = fastpow(base, n - k) * b;
		cout << b[0][0] << endl;
	}
}

signed main() {
	int T;
	cin >> T;
	while (T--)	solve();
	return 0;
}