题解

ACGO 不知道发啥电把原题链接弄没了，还要我手动加。

Problem：A93177

Difficulty：4.8 / Medium+

Tag：随机化

朴素矩乘是 $O(n^3)$ 的，不朴素矩乘是 $O(n^{2.7})$ 的，那咋办？

注意矩阵有两个性质：

• $ABC=A(BC)$。
• 若 $AC=BC$，则 $A=B$。

所以我们可以构造一个 $n\times 1$ 的向量 $D$，分别算出 $ABD$ 和 $CD$，判断这两个结果是否相等。由于矩阵乘向量是 $O(n^2)$ 的，所以这样做就是 $O(n^2)$ 的。

那如何构造呢？答案是随机！

很简单，因为向量的每一个值都相当于 $n$ 个乘积相加模 $998244353$，这么做和字符串哈希很像，这个卡掉的概率也和随机底数下构造两个字符串让它们哈希冲突的概率差不多，为 $\frac{n}{998244353}$，几乎不可能。

namespace cjdst{
    const ll N = 3000, mod = 998244353;
	ll a[N + 5][N + 5], b[N + 5][N + 5], rnd[N + 5], c[N + 5][N + 5], tmp1[N + 5], tmp2[N + 5];
	std::mt19937_64 rng(1590033);
	int n;
	 
	void solve(){
		std::cin >> n;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				std::cin >> a[i][j];
			}
		}
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				std::cin >> b[i][j];
			}
		}
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				std::cin >> c[i][j];
			}
		}
		for(int i = 1; i <= n; i++){
			rnd[i] = rng() % mod;
		}
		memset(tmp1, 0, sizeof(tmp1));// 这个不要学，这里 n 很小可以用，一般多测这个会炸的
		memset(tmp2, 0, sizeof(tmp2));
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				tmp1[i] += b[i][j] * rnd[j];
				tmp1[i] %= mod;
			}
		}
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				tmp2[i] += a[i][j] * tmp1[j];
				tmp2[i] %= mod;
			}
		}
		for(int i = 1; i <= n; i++){
			tmp1[i] = tmp2[i];
			tmp2[i] = 0;
		}
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				tmp2[i] += c[i][j] * rnd[j];
				tmp2[i] %= mod;
			}
		}
		for(int i = 1; i <= n; i++){
			if(tmp1[i] != tmp2[i]){
				std::cout << "No\n";
				return;
			}
		}
		std::cout << "Yes\n";
	}
}

时间复杂度：$O(n^2)$。