札记 循环矩阵

· · 个人记录

模拟赛后学到了有趣的科技——循环矩阵

概念见百度

简单的说，正常矩乘要维护转移矩阵，而循环矩阵矩乘只要一行就够了，复杂度可以被降到n2log

据说，这类问题还可以用多项式乘法降到nloglog，恕我才疏学浅就不说了(

例题可以看这个