morgana专题

2018 ICPC 徐州网络赛 K题 Morgana Net

题意: 求第迭代t次后的矩阵卷积。 题解: 输入给出两个矩阵An,Bm 建立一个矩阵Cn*n,将矩阵A中的元素以此放到矩阵C的第一行 我们将卷积的过程构造成一个转移矩阵,然后用矩阵快速幂解决 构造方法: 考虑点a,它周围的点a1,a2,a3,a4,a5......要参与卷积的计算中 设点a在矩阵C中位于第y列,点ai在矩阵C中位于第xi列 我们将转移矩阵D的D[xi][y