S是初始向量，R是答案向量，A转换矩阵，那么有

R=S*A+S*A^3+S*A^5+...+S*A^(2k+1)

因为矩阵运算满足结合律和分配律
所以有

R=S*A*(I+A^2+A^4+A^6+...+A^(2k))

两边右乘(A^2-I)

得到

R*(A^2-I) = S*A*(I+A^2+A^4+A^6...+A^(2k))*(A^2-I)

根据结合律 和分配律

得到

R*(A^2-I) = S*A*( A^(2k+2) -I)

所以

R= S*A*(A^(2k+2)-I)* (A^2-I)^(-1)

:-)

• 如果直接计算A+A^3+A^5+...+A^(N-(!(N&0x1))) 这样会TLE么。。？ (351) O___O 2008-10-20 13:02:29
• A^2-I 一定可逆吗？ (0) cmc_hope 2008-10-20 16:50:32