Question

一道acm题，求解释求思路

上面是题目描述
Input
The input includes several cases. For each case, there are 3 lines.The first line contains 2 integers N and M (1<=N<=10^8, 1<=M<=10)The second line contains m integers, represent F(0), F(1), F(2)…F(M-1) (-10000<F(i)<10000).The third line contains m integers, represent (-10000< <10000)
Output
For each case, output S(N) mod 10007
Sample Input
14 2
0 1
1 1
Sample Output
986
他有个hint是Martix
表示完全不理解，求解释，求代码
这是Oj网址：http://acm.hfut.edu.cn/OnlineJudge/
第1225题，谢谢了。

Answer 1

这是一个递推数列，可以使用矩阵连乘（于是有log2的二分优化），下面具体分析：

数列的每一项是其之前N项的加权和（权为a[i]），N已知；
于是，我们构造一个行矩阵(1*N)
X(i) = [F(i), F(i-1), ... , F(i-N)]
于是我们可以构造一个矩阵 G, 使得 X(i) = X(i-1) * G
然后，X(i+1) = X(i-1)*(G^2)
X(i+M) = X(i-1)*(G^(M+1))
只要构造出来G,然后用二分法求出 G^(M+1)，即可解得 X(i+M)，即F(i+M)

Answer 2

The third line contains m integers, represent (-10000< <10000)

represent what ?
an是个神马东西
网址就不去