339. Recursive Sequence
4月の忙しい時期を乗り越えた気がするのでSPOJ再開。
次の漸化式を満たす数列のn項目を求める問題。
ただし、n ≦ 1,000,000,000, k ≦ 10。
フィボナッチ数列の一般化っぽい形をしてるので、フィボナッチ数列のn項目をO(logn)で求めるのと同じ方法が使える。
まず k=2 の場合は、n > 2のとき
より
が成り立つ。
k=3の場合は、n > 3のとき
より
が成り立つ。
一般に n > k のとき
となる。
あとはをO(logn)で求めれば終了。
#include <stdio.h> #include <string.h> int b[10], c[10]; long long A[100]; long long B[100]; int M = 1000000000; void mul(long long dest[], const long long lhs[], const long long rhs[], int m) { long long temp[100]; for (int i = 0; i < m; ++i) { for (int j = 0; j < m; ++j) { long long v = 0; for (int k = 0; k < m; ++k) { v += lhs[i*m + k] * rhs[k*m + j]; v %= M; } temp[i*m + j] = v; } } memcpy(dest, temp, m * m * sizeof(long long)); } int main() { int T; scanf("%d", &T); while (T--) { int k; scanf("%d", &k); for (int i = 0; i < k; ++i) scanf("%d", &b[i]); for (int i = 0; i < k; ++i) scanf("%d", &c[i]); int n; scanf("%d", &n); memset(A, 0, sizeof(A)); memset(B, 0, sizeof(B)); for (int i = 0; i < k; ++i) A[i] = c[i]; for (int i = 1; i < k; ++i) A[i*k + i-1] = 1; for (int i = 0; i < k; ++i) B[i*k + i] = 1; if (n >= k) { n -= k; while (n > 0) { if (n & 1) mul(B, B, A, k); mul(A, A, A, k); n >>= 1; } long long v = 0; for (int i = 0; i < k; ++i) { v += B[i] * b[k-i-1]; v %= M; } printf("%lld\n", v); } else { printf("%d\n", b[n-1]); } } }