3/24
3318 Matrix Multiplication
行列検算。乱択アルゴリズムでよくある問題。
AB=Cにおいて各要素をランダムに選んで作ったベクトルxを右からかけると、
ABx=Cxとなり両辺ともO(n^2)で計算可能となる。
AB=Cであれば任意のｘで常に等号を満たし、そうでなければ満たさない場合がある。
xの要素を確率1/2で独立に0,1を選んだとすると、(たしか)失敗確率1/2の片側誤りアルゴリズムになり、
検算をk回繰り返すことでO(kn^2)で失敗確率O(1/2^k)のアルゴリズムになる。
実際にはxの要素をある程度大きな集合から選べば、失敗しにくくなる。
本問題では0から100までの要素から選んでベクトルを生成したら、k=1でAcceptだった。
