LargeDumpling

我只负责打字,内容我也不知道从何而来。

LYDSY 3583 杰杰的女性朋友

传送门

        一眼发现是矩乘,然后发现会T掉。Drz

        强行矩乘果然是不行,得使用一些特♂殊的技♂巧优化方法才能通过。

        在原图中G[u][v]=Σout[u][k]*in[v][k],即,G=out X in,所以答案G^d=(out X in)^d=out X in X out X in X ...... out X in X out X in=out X (in X out)^(d-1) X in,这样我们将原来需要用快速幂计算的1000*1000的矩阵变成了20*20的小矩阵,一下子就优化了!也许类似的长方形的矩阵连乘也可以缩小需要快速幂的矩阵?对!

        对于每一个询问(u,v,d)我们倍增出(也许也可以提前预处理?)(in X out)^(d-1),并设这个倍增出来的矩阵为A,则枚举一个k1和k2,Σout[u][k1]*A[k1][k2]*in[v][k2]就是答案。

AC代码

评论 ( 4 )
热度 ( 2 )

© LargeDumpling | Powered by LOFTER