339. Recursive Sequence - nojimaの日記

4月の忙しい時期を乗り越えた気がするのでSPOJ再開。

https://www.spoj.pl/problems/SEQ/

次の漸化式を満たす数列 $\{a_i\}$ のn項目を求める問題。
$a_i=\left\{ \begin{array}{ll} b_i & (i \leq k) \\ c_1a_{i-1} + c_2a_{i-2} + \cdots + c_ka_{i-k} & (i > k) \end{array} \right.$
ただし、n ≦ 1,000,000,000, k ≦ 10。

フィボナッチ数列の一般化っぽい形をしてるので、フィボナッチ数列のn項目をO(logn)で求めるのと同じ方法が使える。
まず k=2 の場合は、n > 2のとき

$\left(\begin{array}{c}a_n \\ a_{n-1} \end{array} \right) = \left( \begin{array}{cc} c_1 & c_2 \\ 1 & 0 \end{array} \right) \left( \begin{array}{c} a_{n-1} \\ a_{n-2} \end{array} \right)$

より

$\left(\begin{array}{c}a_n \\ a_{n-1} \end{array} \right) = \left( \begin{array}{cc} c_1 & c_2 \\ 1 & 0 \end{array} \right)^{n-2} \left( \begin{array}{c} b_{2} \\ b_{1} \end{array} \right)$

が成り立つ。

k=3の場合は、n > 3のとき

$\left(\begin{array}{c}a_n \\ a_{n-1} \\ a_{n-2} \end{array} \right) = \left( \begin{array}{ccc} c_1 & c_2 & c_3 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{array} \right) \left( \begin{array}{c} a_{n-1} \\ a_{n-2} \\ a_{n-3} \end{array} \right)$

より

$\left(\begin{array}{c}a_n \\ a_{n-1} \\ a_{n-2} \end{array} \right) = \left( \begin{array}{ccc} c_1 & c_2 & c_3 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{array} \right)^{n-3} \left( \begin{array}{c} b_{3} \\ b_{2} \\ b_{1} \end{array} \right)$

が成り立つ。

一般に n > k のとき

$\left(\begin{array}{c}a_n \\ a_{n-1} \\ \vdots \\ a_{n-k+1} \end{array} \right) = \left( \begin{array}{ccccc} c_1 & c_2 & \cdots & c_{k-1} & c_k \\ 1 & & & & \\ & 1 & & & \\ & & \ddots & & \\ & & & 1 & \end{array} \right)^{n-k} \left( \begin{array}{c} b_{k} \\ b_{k-1} \\ \vdots \\ b_{1} \end{array} \right)$

となる。

あとは $\left( \begin{array}{ccccc} c_1 & c_2 & \cdots & c_{k-1} & c_k \\ 1 & & & & \\ & 1 & & & \\ & & \ddots & & \\ & & & 1 & \end{array} \right)^{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]);
        }
    }
}