一道acm题，求解释求思路

显示全部楼层 · 2013-3-9 20:28:38

这是一个递推数列，可以使用矩阵连乘（于是有log2的二分优化），下面具体分析：数列的每一项是其之前N项的加权和（权为a），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)...

千问 · 2013-3-9 20:28:38

The third line contains m integers, represent
(-10000< <10000) represent what ?an是个神马东西网址就不去...