Description

The Association for Courtly Manners, an international organization for standardization of social interactions (Better known under the name Absurdly Clumsy Moralists, but let's not take prejudice.) has decided to create a new international standard defining ranks of firepersons (Formerly firemen, but the international standards of course must be politically correct.) - each fireperson receives an integer number describing his rank and when they arrive to a fire, they must enter the fire ground in order of increasing ranks and the low ranked firepersons must keep the fire burning long enough for the high ranked firepersons to enjoy extinguishing sufficiently.

The ranks are assigned according to an Arbitrary Constant Multiplier Sequence. An ACM-sequence of order k is an integer sequence defined by its first k terms a0, a1,...ak-1 and a recurrence relation an=Σ1<=i<=kan-ibi mod 10 000 for n >= k, where the bi's are integer constants. The i-th oldest fireperson then gets rank ai.

Your task is to calculate the rank of the i-th fireperson, given parameters of the ACM-sequence and the number i.

Input

The input consists of several instances. Each instance is described on a single line containing the following integers separated by a single space: k, a0, , ak-1, b1, , bk, i. Here 1 <= k <= 100 is the order of the sequence, 0 <= ai < 10 000 are the first k elements of the sequence, 0 <= bi < 10 000 are the multipliers and 0 <= i < 1 000 000 000 is the number of the element we ask for.

The input ends with a line containing a number 0.

Output

The output consists of several lines corresponding to the instances on the input. The l-th line contains a single integer ai which is the i-th element of the sequence described by the l-th input instance.

输入数据 1 2 0 1 1 1 6 0 输出数据 1 8

Source

CTU Open 2004

描述

宫廷礼仪协会（一个致力于社交互动标准化的国际组织，更广为人知的名称是 “荒谬笨拙的道德家”，但我们不应该有偏见）决定创建一个新的国际标准来定义消防员（以前叫消防员，但国际标准当然必须符合政治正确性）的等级。每个消防员会得到一个整数来表示他的等级。当他们到达火灾现场时，必须按照等级从小到大的顺序进入火场，低等级的消防员必须让火势持续燃烧足够长的时间，以便高等级的消防员能充分享受灭火的过程。等级是根据任意常数乘数序列（ACM - 序列）来分配的。

一个阶数为 k 的 ACM 序列是一个整数序列，由它的前 k 项 a_0, a_1,..., a_{k - 1} 以及递推关系 a_n=(sum_{1<=i<=k}a_{n - i}*b_i)mod10000其中 n>=k且b_i为整数常数定义。第 i 年长的消防员将获得等级a_i。你的任务是根据 ACM 序列的参数和数字 i，计算第 i 个消防员的等级。

输入

输入包含多个实例。每个实例在一行中描述，包含以下由单个空格分隔的整数：k, a_0, ..., a_{k - 1}, b_1, ..., b_k, i。其中1<=k<=100是序列的阶数，0<=a_i <10000 是序列的前 k 个元素，0<=b_i <10000是乘数，0<= i < 1000000000是我们要查询的元素的编号。输入以包含数字 0 的一行结束。

输出

输出包含若干行，对应输入中的实例。第 l 行包含一个整数 a_i，它是第 l 个输入实例所描述序列的第 i 个元素。

输入数据 1

2 0 1 1 1 6

0

输出数据 1

8

来源2004 年 CTU 公开赛

算法标签：

递推，线性代数，矩阵相乘，快速幂

题意分析：

利用给出的关系a_n=(sum_{1<=i<=k}a_{n - i}*b_i)mod10000其中 n>=k且b_i为整数常数定义，来求解第i项的a_i.

解题思路：

因为值很多，用常规的直接递推求解会超时，所以这里利用矩阵快速幂来求解； 使用矩阵快速幂算法计算A^{i - k + 1}，然后将其与初始向量begin{bmatrix}a_{k - 1}a_{k - 2},...,a_{0}end{bmatrix}相乘，得到的结果向量的第一个元素就是a_i.

##标程

#include <iostream>
#include <cstring>
using namespace std;

int x, k, a[110], b[110], c[110][110], e[110][110];

// 矩阵乘法函数
void f(int c[110][110], int d[110][110]) {
    int dd[110][110];
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= k; j++) {
            int t = 0;
            for (int l = 1; l <= k; l++) {
                t += (c[i][l] * d[l][j]) % 10000;
            }
            dd[i][j] = t % 10000;
        }
    }
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= k; j++) {
            c[i][j] = dd[i][j];
        }
    }
}

// 矩阵快速幂函数
void mi(int n) {
    while (n != 0) {
        if (n % 2 == 1) {
            f(e, c);
        }
        f(c, c);
        n /= 2;
    }
}

int main() {
    int sum = 0;
    while (cin >> k) {
        sum = 0;
        if (k == 0) {
            break;
        }
        memset(c, 0, sizeof(c));
        memset(e, 0, sizeof(e));
        for (int i = 1; i <= k; i++) {
            for (int j = 1; j <= k; j++) {
                if (i == j) {
                    e[i][j] = 1;
                }
            }
        }
        for (int i = 0; i < k; i++) {
            cin >> a[i];
        }
        for (int i = 1; i <= k; i++) {
            cin >> b[i];
            c[1][i] = b[i];
        }
        for (int i = 2; i <= k; i++) {
            for (int j = 1; j <= k; j++) {
                if (i - 1 == j) {
                    c[i][j] = 1;
                }
            }
        }
        cin >> x;
        if (x >= k) {
            mi(x - k + 1);
            for (int i = 1; i <= k; i++) {
                sum += (e[1][i] * a[k - i]) % 10000;
            }
            sum = sum % 10000;
            cout << sum << endl;
        } else {
            cout << a[x] << endl;
        }
    }
    return 0;
}