作业帮一道acm题,求解释求思路
来源：学生作业帮 编辑：作业帮 分类：数学作业 时间：2024/05/16 17:14:51
一道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
表示完全不理解,求代码
第1225题,
上面是题目描述
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
表示完全不理解,求代码
第1225题,
这是一个递推数列,可以使用矩阵连乘（于是有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)
数列的每一项是其之前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)