問題
$N \times M$ 行列 $A$（各要素は $\mathbb{F}_p$, $p = 998244353$）が与えられる。$Q$ 個のクエリを処理せよ。
制約
$1 \le N, M \le 300$
$1 \le Q \le 10^4$
$0 \le A[i][j] < p$
時間制限: 3sec / メモリ: 256MB
クエリ種別
| 種別 | 形式 | 意味 |
|---|---|---|
| 更新 | 1 i j v | $A[i][j] \leftarrow v$ に変更 |
| クエリ | 2 | 現在の行列 $A$ のランクを答える |
入出力例
入力例 1
3 3 2
1 2 3
4 5 6
7 8 9
2
1 1 3 0
2出力例 1
2
3初期行列はランク2（行3=行1+行2の定数倍）。A[1][3]=0 にすると行1列が変わりランク3に。
概念図: Gauss 消去法の手順
ヒント（段階的開示）
ヒント1: 方向性
行列ランクは Gauss 消去法（前進消去）で $O(N^2 M)$ で計算できる。
クエリ型では毎回 Gauss 消去を行う単純実装で $O(Q \cdot N^2 M)$。$N,M \le 300$, クエリ2の回数が少なければ通る。
ヒント2: アプローチ
- 行列のコピーを作成（元の行列を破壊しない）
- 列を左から順にピボット選択
- ピボット行を選んで rank 行目に swap
- そのピボット列を他のすべての行から消去
- rank = ピボットを立てた列数
ヒント3: 実装骨格
MOD = 998244353
def gauss_rank(mat, N, M):
A = [row[:] for row in mat]
rank = 0
for col in range(M):
pivot = -1
for row in range(rank, N):
if A[row][col] != 0:
pivot = row; break
if pivot == -1: continue
A[rank], A[pivot] = A[pivot], A[rank]
inv = pow(A[rank][col], MOD - 2, MOD)
for j in range(col, M):
A[rank][j] = A[rank][j] * inv % MOD
for row in range(N):
if row != rank and A[row][col] != 0:
f = A[row][col]
for j in range(col, M):
A[row][j] = (A[row][j] - A[rank][j] * f) % MOD
rank += 1
return rank模範解答 (Python)
import sys
input = sys.stdin.readline
MOD = 998244353
def solve():
N, M, Q = map(int, input().split())
mat = []
for _ in range(N):
mat.append(list(map(int, input().split())))
def gauss_rank():
A = [row[:] for row in mat]
rank = 0
for col in range(M):
pivot = -1
for row in range(rank, N):
if A[row][col] != 0:
pivot = row
break
if pivot == -1:
continue
A[rank], A[pivot] = A[pivot], A[rank]
inv = pow(A[rank][col], MOD - 2, MOD)
for j in range(col, M):
A[rank][j] = A[rank][j] * inv % MOD
for row in range(N):
if row != rank and A[row][col] != 0:
factor = A[row][col]
for j in range(col, M):
A[row][j] = (A[row][j] - A[rank][j] * factor) % MOD
rank += 1
return rank
out = []
for _ in range(Q):
line = input().split()
if line[0] == '1':
i, j, v = int(line[1])-1, int(line[2])-1, int(line[3])
mat[i][j] = v % MOD
else:
out.append(gauss_rank())
print('\n'.join(map(str, out)))
solve()
Step-by-Step 解説
1Gauss 消去法の基本
列を左から順にピボットを選ぶ。ピボット行を選び、その列の他の全行を消去（行基本変形）。ランク = ピボットを立てた列の数。
列を左から順にピボットを選ぶ。ピボット行を選び、その列の他の全行を消去（行基本変形）。ランク = ピボットを立てた列の数。
2mod p の逆元
$\mathbb{F}_p$ 上では割り算 = 逆元の乗算。
$\mathbb{F}_p$ 上では割り算 = 逆元の乗算。
pow(x, MOD-2, MOD) でフェルマーの小定理による逆元計算（$O(\log p)$）。実数と違い数値誤差がないため、任意の非零要素をピボットにできる。
3数値的安定性
実数 Gauss 消去では部分ピボット選択（絶対値最大の行を選択）が数値安定性に必要。mod p では任意の非零要素をピボットにできるため、単純な「最初に見つかった非零行」で十分。
実数 Gauss 消去では部分ピボット選択（絶対値最大の行を選択）が数値安定性に必要。mod p では任意の非零要素をピボットにできるため、単純な「最初に見つかった非零行」で十分。
4差分更新の工夫
行追加時のランク変化: 新しい行が既存の線形結合なら +0、独立なら +1。既約行階段形に変換済みの行列に 1 行追加するとき $O(N)$ で判定可能（行を消去して非零チェック）。
行追加時のランク変化: 新しい行が既存の線形結合なら +0、独立なら +1。既約行階段形に変換済みの行列に 1 行追加するとき $O(N)$ で判定可能（行を消去して非零チェック）。
計算量
Gauss 消去 1回: $O(N^2 M)$（$N \le M$ の場合 $O(N^2 M)$）
全体: $O(Q_2 \cdot N^2 M)$（$Q_2$ = クエリ2の回数）
$N=M=300, Q_2=10^4$: 最悪 $3 \times 10^{11}$ → クエリ2の頻度に依存
空間: $O(NM)$
全体: $O(Q_2 \cdot N^2 M)$（$Q_2$ = クエリ2の回数）
$N=M=300, Q_2=10^4$: 最悪 $3 \times 10^{11}$ → クエリ2の頻度に依存
空間: $O(NM)$
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
inv = 1 / A[rank][col] | float 誤差・mod p 不正 | pow(A[rank][col], MOD-2, MOD) |
range(M) で全列処理 | 左の列は既に0なので不要 | range(col, M) で効率化 |
| 行列のコピーを忘れてオリジナルを破壊 | A = mat はシャロウコピー | A = [row[:] for row in mat] |
| rank の初期化忘れ | ループ外で rank=0 を宣言 | rank = 0 を消去前に設定 |
次のステップ
- 発展問題: オンライン行列ランク維持（行追加/削除をストリームで処理）
- 類題: Library Checker "Determinant of Matrix"、CF 280E
- 応用: 連立方程式の解の存在判定・線形空間の次元計算