@可爱即是正义

矩阵乘法还有一个叫做取模优化，若mod在1e9级别

先全开unsigned long long令const unsigned long long Q=16ull*mod*mod

只要保证Q+mod*mod<MAX就行了

然后可以if(a[i][j]>=Q)a[i][j]-=Q

最后再对a[i][j]%=mod，这样取模操作就只有$O(n^2)$次了

当然，你可能只需要一个long long的临时数组，a开long long有可能导致变慢

有时候，该优化的作用远远大于ikj缓存优化

还有，你在第二个循环判个0，对于一些特殊矩阵（比如有一个区域永远是0）会降低复杂度

更高级的还有让编译器帮你并行优化，就是编译器用一些avx/sse指令集（具体我也不太清楚）实现并行操作。循环展开可以刺激编译器优化，当然更好是自己使用那些函数。

还有就是分块矩阵乘法，因为矩阵太大塞不进缓存，分块后就可以使用缓存。这样可以大大提高命中率。可以自行搜索相关资料

当然复杂度降低可以使用strassen算法(虽然并不会快，只是复杂度变低了而已)

下面那个次数优化就叫做最优矩阵链乘问题

@万岁 https://www.luogu.org/blog/woshisb/post-ss

感谢投稿，.....你觉得我会让你过吗

@chengni https://www.luogu.org/blog/[chengni](/space/show?uid=60136)5673/er-jin-zhi-yu-wei-yun-suan

唉那好吧，你就再说几句：

bitset是用uint/long long类型来实现每次同时操作32/64个01变量的东西，所以他的很多操作都是O(1)或O(n/32)/O(n/64)的

至于是32还是64，一般看机器是32位还是64位。