?

题意：一个矩阵N*K的矩阵A，一个K*N的矩阵B，(4 <= N <= 1000,2 <=K <= 6)。先进行矩阵乘法C=A*B，然后进行D=C^（N*N）的幂运算，然后对D的每个数对6取模，最后求出D的所有位置数字之和。

思路：像之前那道矩阵乘法一样，特别大的矩阵直接进行乘法在没有小规律的帮助时是不可能直接过的（目前看即使是Strassen矩阵算法也不会加速到要求以内）题目中给的C矩阵是1000*1000的矩阵进行快速幂是一定超时的，所以我注意到了A矩阵的列数和B矩阵的行数K是不超过六的，而6*6的矩阵进行快速幂是没问题的。D=A*B*A*B*...*A*B*A*B，可以看成D=A*(B*A*...*B*A)*B。这样既不影响矩阵左乘和右乘的关系，又能防止行列数太大爆掉。（题里的小细节是挺厉害的，首先爆栈的问题需要解决，然后还有矩阵的赋值运算也是O(N)的复杂度）

代码：

?

#pragma comment(linker, /STACK:1024000000,1024000000)
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include