暴力矩阵乘法显然不能过,我们考虑随机。
进行 O(1)O(1)O(1) 次随机,每次随机一个向量,把它和 a,ba,ba,b 相乘,也把它和 ccc 相乘。
最终把两个向量比较一下是否相同即可。正确性显然很高,事实上一次随机就过了。
复杂度 O(Tn2)O(Tn^2)O(Tn2)
注册一个 BZOJ by HydroOJ 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 HydroOJ 通用账户