ACGO 不知道发啥电把原题链接弄没了，还要我手动加。 Problem：A93177 Difficulty：4.8 / Medium+ Tag：随机化 朴素矩乘是 O(n3)O(n^3)O(n3) 的，不朴素矩乘是 O(n2.7)O(n^{2.7})O(n2.7) 的，那咋办？ 注意矩阵有两个性质： * ABC=A(BC)ABC=A(BC)ABC=A(BC)。 * 若 AC=BCAC=BCAC=BC，则 A=BA=BA=B。 所以我们可以构造一个 n×1n\times 1n×1 的向量 DDD，分别算出 ABDABDABD 和 CDCDCD，判断这两个结果是否相等。由于矩阵乘向量是 O(n2)O(n^2)O(n2) 的，所以这样做就是 O(n2)O(n^2)O(n2) 的。 那如何构造呢？答案是随机！ 很简单，因为向量的每一个值都相当于 nnn 个乘积相加模 998244353998244353998244353，这么做和字符串哈希很像，这个卡掉的概率也和随机底数下构造两个字符串让它们哈希冲突的概率差不多，为 n998244353\frac{n}{998244353}998244353n ，几乎不可能。 时间复杂度：O(n2)O(n^2)O(n2)。