Day 073-Q5 — Freivalds 法・行列積検証（Schwartz-Zippel 補題）

問題

$N \times N$ の整数行列 $A$, $B$, $C$ が与えられる。$AB = C$ が成り立つかどうかを、誤り確率 $\le 2^{-30}$ 以下で判定せよ。

ただし、使用できる計算量は $O(N^2 \log(1/\delta))$ であり、$O(N^3)$ の直接計算は時間制限（2秒）内に間に合わない。

ランダムベクトルを使った検証のみで正しく判定すること。

入出力例

3
1 0 0
0 1 0
0 0 1
2 3 5
7 11 13
17 19 23
2 3 5
7 11 13
17 19 23

YES

NO

概念図: Freivalds 法の仕組み

ヒント

MOD = (1 << 61) - 1  # メルセンヌ素数

def mat_vec_mod(M, v):
    n = len(M)
    result = []
    for i in range(n):
        s = sum(M[i][j] * v[j] for j in range(n))
        result.append(s % MOD)
    return result

for _ in range(40):
    r = [random.randrange(MOD) for _ in range(N)]
    u = mat_vec_mod(B, r)
    v = mat_vec_mod(A, u)
    w = mat_vec_mod(C, r)
    if v != w:
        print("NO"); return
print("YES")

模範解答

import sys
import random
input = sys.stdin.readline
MOD = (1 << 61) - 1  # メルセンヌ素数（2^61-1）

def mat_vec_mod(M, v):
    """N×N 行列 × N ベクトル の積 mod (2^61-1)"""
    n = len(M)
    result = []
    for i in range(n):
        s = 0
        row = M[i]
        for j in range(n):
            s += row[j] * v[j]
        result.append(s % MOD)
    return result

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1

    A = []
    for i in range(N):
        row = [int(data[idx+j]) for j in range(N)]
        A.append(row); idx += N

    B = []
    for i in range(N):
        row = [int(data[idx+j]) for j in range(N)]
        B.append(row); idx += N

    C = []
    for i in range(N):
        row = [int(data[idx+j]) for j in range(N)]
        C.append(row); idx += N

    # Freivalds 法: 40回繰り返しで誤り確率 ≤ 2^{-40}
    TRIALS = 40
    for _ in range(TRIALS):
        r = [random.randrange(MOD) for _ in range(N)]
        u = mat_vec_mod(B, r)
        v = mat_vec_mod(A, u)
        w = mat_vec_mod(C, r)
        if v != w:
            print("NO")
            return

    print("YES")

solve()

Step-by-Step 解説

Step 1: Freivalds 法の原理

$AB = C$ を確認したい。もし $AB \ne C$ なら、ある $(i,j)$ で $(AB)_{ij} \ne C_{ij}$。

Schwartz-Zippel 補題: 非零多項式 $f(r_1,\ldots,r_N)$ に対して、有限集合 $S$ からランダムに選んだ $r$ で $f(r)=0$ となる確率は $\le \deg(f)/|S|$。

$AB \ne C$ の場合、$(AB - C)r$ は $r$ に関して 1 次の非零多項式なので、$r \in \{0,1\}^N$ からランダムに選んだ場合に一致する確率は $\le 1/2$。

Step 2: 計算量の分析

各試行: $Br \to O(N^2)$、$A(Br) \to O(N^2)$、$Cr \to O(N^2)$。$k=40$ 試行で $O(40N^2)$。$N=1000$ なら $4 \times 10^7$ 演算。

Step 3: より大きな素数でのランダム化

$r \in \mathbb{Z}_p^N$（$p = 2^{61}-1$, メルセンヌ素数）を使うと誤り確率が $\le N/p \approx 10^{-15}$ に激減。$\{0,1\}^N$ より格段に強い保証。

Step 4: 実際の応用場面

• 多項式恒等式の検証（$f(x) \equiv 0$?）
• グラフの完全マッチング存在判定（Edmonds 行列のランクが $N$ か）
• 行列ランクの確率的計算

よくあるミス

次のステップ

• 発展: 一般の多項式恒等式 $f(x_1,\ldots,x_n) \equiv 0$ の確率的検証
• 発展: Schwartz-Zippel 補題を用いた完全二部マッチング存在判定（Edmonds 行列）
• 発展: ランダム行列のランク計算（線形基底と Freivalds 法の融合）

自己評価