Day 049-Q5 — Schwartz–Zippel補題 + ランダム化行列積零行列判定

2026-06-02 赤色 Master / Phase 8+ ★★★★★★★★★ Schwartz–Zippel / スパーステーブル行列積 / 多点評価

問題

$N$ 個の行列 $M_1, M_2, \ldots, M_N$（各 $d \times d$, 整数要素）が与えられる。$Q$ 個のクエリ $(l_i, r_i)$ それぞれについて、積 $M_{l_i} \cdot M_{l_i+1} \cdots M_{r_i}$ が零行列かどうかを高速に判定せよ。

各行列の要素は $[0, p)$（$p = 998244353$）に属する整数で与えられ、積の計算も $\bmod p$ で行う。

制約

$1 \le N \le 10^4$
$1 \le d \le 4$
$1 \le Q \le 10^5$
$1 \le l_i \le r_i \le N$
$p = 998244353$
時間制限: 3秒

入出力例

入力例 1

3 2 2
1 0
0 0
0 1
0 0
1 0
0 1
1 2
1 3

出力例 1

Yes
Yes

$M_1=[[1,0],[0,0]]$, $M_2=[[0,1],[0,0]]$, $M_3=[[1,0],[0,1]]$。$M_1 M_2=[[0,1],[0,0]]\cdot...$は実際に計算して確認。

概念図: Schwartz–Zippel 補題による零行列判定

Schwartz–Zippel 補題: ランダムベクトルで零行列を確率的判定 v ∈ F_p^d ランダムベクトル スパーステーブル sparse[k][i] = M_i...M_{i+2^k-1} クエリ (l, r) M_l...M_r の積 w = M_l...M_r · v を計算（O(log N · d²) でベクトル作用） w ≠ 0 → 確実に非零行列 w = 0 → 高確率で零行列 誤判定確率 ≤ d/p

ヒント（段階的開示）

ヒント1: 方向性
行列積が零行列かどうかを全クエリで毎回計算すると $O(Q \cdot N \cdot d^3)$ となり TLE。Schwartz-Zippel 補題を使い、ランダムベクトルとの積で零行列を高確率で判定できます。
ヒント2: スパーステーブルで行列積を高速化
$\text{sparse}[k][i] = M_i \cdots M_{i+2^k-1}$（$2^k$ 個の行列の積）を前計算（$O(N \log N \cdot d^3)$）し、クエリ $(l, r)$ を $O(\log N \cdot d^3)$ で分解します。
ヒント3: Schwartz–Zippel の適用骨格 
import random
p = 998244353
K = 3  # ランダムベクトルの本数

# K 本のランダムベクトル（0 を避ける）
rands = [[random.randrange(1, p) for _ in range(d)] for _ in range(K)]

def mat_vec(M, v):
    # M×v の計算
    return [(sum(M[i][j] * v[j] for j in range(d))) % p for i in range(d)]

# クエリ (l, r) の処理
M_prod = query_mat(l, r)  # スパーステーブルから積を取得
is_zero = all(
    all(x == 0 for x in mat_vec(M_prod, v))
    for v in rands
)

模範解答 (Python)

import sys
import random
from sys import stdin

def solve():
    data = stdin.buffer.read().split()
    idx = 0
    N, d, Q = int(data[idx]), int(data[idx+1]), int(data[idx+2]); idx += 3
    p = 998244353

    mats = []
    for i in range(N):
        M = []
        for r in range(d):
            row = [int(data[idx+c]) for c in range(d)]
            idx += d
            M.append(row)
        mats.append(M)

    def mat_vec(M, v):
        res = []
        for row in M:
            s = 0
            for j in range(d):
                s += row[j] * v[j]
            res.append(s % p)
        return res

    def mat_mul(A, B):
        res = [[0]*d for _ in range(d)]
        for i in range(d):
            for k in range(d):
                if A[i][k] == 0: continue
                for j in range(d):
                    res[i][j] = (res[i][j] + A[i][k] * B[k][j]) % p
        return res

    LOG = max(1, N.bit_length())

    # sparse[k][i] = M_i * ... * M_{i+2^k-1}  (1-indexed)
    sparse = [[None] * (N + 2) for _ in range(LOG + 1)]
    for i in range(1, N + 1):
        sparse[0][i] = mats[i - 1]

    for k in range(1, LOG + 1):
        for i in range(1, N + 1):
            half = 1 << (k - 1)
            j = i + half
            if j <= N:
                sparse[k][i] = mat_mul(sparse[k-1][i], sparse[k-1][j])

    def query_mat(l, r):
        result = None
        i = l
        for k in range(LOG, -1, -1):
            if i + (1 << k) - 1 <= r:
                part = sparse[k][i]
                if result is None:
                    result = part
                else:
                    result = mat_mul(result, part)
                i += 1 << k
        return result

    # Randomized zero test with K vectors
    K = 3
    rands = [[random.randrange(1, p) for _ in range(d)] for _ in range(K)]

    out = []
    for _ in range(Q):
        l, r = int(data[idx]), int(data[idx+1]); idx += 2
        M_prod = query_mat(l, r)

        is_zero = True
        for v in rands:
            result = mat_vec(M_prod, v)
            if any(x != 0 for x in result):
                is_zero = False
                break

        out.append('Yes' if is_zero else 'No')

    sys.stdout.write('\n'.join(out) + '\n')

solve()

Step-by-Step 解説

1Schwartz–Zippel 補題
多変数多項式 $F \not\equiv 0$（次数 $d$）をランダム点で評価したとき $F = 0$ になる確率は $\le d/|\mathbb{F}|$。$p = 998244353$ では誤判定確率 $\le d/p \approx 4/10^9$。
2行列の零行列判定への適用
ランダム $\mathbf{v}$ で $M\mathbf{v} \ne \mathbf{0}$ なら確実に非零行列。$M\mathbf{v} = \mathbf{0}$ でも $M = 0$ でないケースは低確率です。
3スパーステーブル構築
$\text{sparse}[k][i] = M_i \cdots M_{i+2^k-1}$ を $O(N \log N \cdot d^3)$ で前計算。クエリ $(l, r)$ の積を $O(\log N \cdot d^3)$ で計算します。
4ベクトル評価
行列積 $M$ を明示的に持ち、$K$ 本のランダムベクトル $\mathbf{v}$ で $M\mathbf{v}$ を評価します。全て 0 なら零行列と判定。
5誤判定確率の管理
$K$ 本の独立ベクトルで誤判定確率 $\le (d/p)^K$。$K=3, d=4$ では約 $10^{-26}$。実用上は 1 本でも十分です。

計算量

スパーステーブル構築: $O(N \log N \cdot d^3)$
各クエリ: $O(\log N \cdot d^3 + K \cdot d^2)$
全体: $O(N \log N \cdot d^3 + Q \log N \cdot d^2)$
空間: $O(N \log N \cdot d^2)$

よくあるミス

ミス原因正しい書き方
スパーステーブルの順序を逆にする$M_l \cdots M_r$ の順序sparse[k][i] = sparse[k-1][i] × sparse[k-1][i+2^{k-1}]
ベクトルがすべて 0 のとき$\mathbf{v}=\mathbf{0}$ では常に $M\mathbf{v}=\mathbf{0}$random.randrange(1, p) で 0 を避ける
誤判定方向を誤解$M\mathbf{v}=0$ は確定でない「$M\mathbf{v}\ne 0$ なら確実に非零行列」のみ確定
LOG の計算漏れ$N=1$ のとき LOG=0LOG = max(1, N.bit_length())

次のステップ

  • 発展問題: ランダム行列フィンガープリンティングで2つの多項式が等しいか判定（Day026 Q5 の復習）
  • 関連: Schwartz-Zippel を使った完全マッチング判定（Edmonds 行列）
  • 応用: 区間行列積を永続データ構造で管理するオンライン版

自己評価