hdu 4965 Fast Matrix Calculation (矩阵快速幂,2014多校#9)

题目链接

题意:Step 1: Calculate a new N*N matrix C = A*B.
Step 2: Calculate M = C^(N*N).
Step 3: For each element x in M, calculate x % 6. All the remainders form a new matrix M’.
Step 4: Calculate the sum of all the elements in M’.

思路: 水题。。就一个trick…

朴素的矩阵乘法的复杂度是n^3的。。。按照题目的顺序求的话。。。。求M矩阵时会超时。。。(而且1000*1000的数组也不能放到结构体里…?

我们可以根据矩阵乘法的结合律。

M = (A*B)^(N*N) = A * (B*A)^(N*N-1) * B

然后就可以搞了。

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz