Day 032-Q4 | Toeplitz行列・Circulant行列とFFT

問題

$N \times N$ の Toeplitz 行列 $T$ が与えられる。Toeplitz行列とは、各対角線上の要素が一定な行列で、$T[i][j] = a[i-j]$ と定義される。

長さ $2N-1$ の整数列 $a[-(N-1)], \ldots, a[0], \ldots, a[N-1]$ と長さ $N$ のベクトル $x$ が与えられる。以下の問いに答えよ。

行列ベクトル積: $y = Tx$ を計算。$O(N^2)$ 未満（$N \le 10^6$）
累乗: $T^K x \bmod p$ を計算（$K \le 10^{18}$、$N \le 10^3$）
行列式: $\det(T) \bmod p$ を計算（$N \le 10^3$）

入力形式 (小問1)

1
N
a[-(N-1)] ... a[N-1]
x[0] ... x[N-1]

制約

小問1: $1 \le N \le 10^6$

小問1: $|a_i|, |x_i| \le 10^9$

小問2,3: $1 \le N \le 10^3$

$1 \le K \le 10^{18}$, $p$ 素数

入出力例

入力例 1 (小問1)

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

出力例 1

3 5 3 6

ヒント (段階的開示)

ヒント1: 方向性

Toeplitz行列ベクトル積は畳み込みと等価。FFT で $O(N \log N)$。

ヒント2: アプローチ

$(Tx)[i] = \sum_j a[i-j] x[j]$ は $a$ と $x$ の線形畳み込みの一部。長さ $2N-1$ の畳み込みを計算し $[N-1, 2N-2]$ を抽出。

ヒント3: 誘導

from numpy.fft import fft, ifft
A = fft(a, n=size)
X = fft(x, n=size)
conv = np.real(ifft(A * X))
y = conv[N-1 : 2*N-1]

模範解答 (Python)

import sys
import numpy as np
from numpy.fft import fft, ifft

def main():
    data = sys.stdin.read().split()
    ptr = 0

    def rd():
        nonlocal ptr
        v = data[ptr]; ptr += 1
        return v

    subproblem = int(rd())

    if subproblem == 1:
        N = int(rd())
        a = np.array([int(rd()) for _ in range(2*N-1)], dtype=np.float64)
        x = np.array([int(rd()) for _ in range(N)], dtype=np.float64)

        size = 1
        while size < 3 * N:
            size <<= 1

        A = fft(a, n=size)
        X = fft(x, n=size)
        conv = np.real(ifft(A * X))
        y = np.round(conv[N-1:2*N-1]).astype(int)
        print(*y)

    elif subproblem == 2:
        N, K, p = int(rd()), int(rd()), int(rd())
        a_vals = [int(rd()) % p for _ in range(2*N-1)]
        x = [int(rd()) % p for _ in range(N)]

        def build_matrix(a_vals, N, p):
            T = [[0]*N for _ in range(N)]
            for i in range(N):
                for j in range(N):
                    T[i][j] = a_vals[i - j + N - 1] % p
            return T

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

        def mat_vec(A, v, N, p):
            res = [0] * N
            for i in range(N):
                for j in range(N):
                    res[i] = (res[i] + A[i][j] * v[j]) % p
            return res

        T = build_matrix(a_vals, N, p)
        result = x[:]
        base = T
        while K > 0:
            if K & 1:
                result = mat_vec(base, result, N, p)
            base = mat_mul(base, base, N, p)
            K >>= 1
        print(*result)

    else:
        N, p = int(rd()), int(rd())
        a_vals = [int(rd()) % p for _ in range(2*N-1)]

        A = [[a_vals[i - j + N - 1] % p for j in range(N)] for i in range(N)]
        det = 1
        for col in range(N):
            pivot = -1
            for row in range(col, N):
                if A[row][col] != 0:
                    pivot = row
                    break
            if pivot == -1:
                print(0); return
            if pivot != col:
                A[col], A[pivot] = A[pivot], A[col]
                det = (-det) % p
            det = det * A[col][col] % p
            inv = pow(A[col][col], p-2, p)
            for row in range(col + 1, N):
                factor = A[row][col] * inv % p
                for c in range(col, N):
                    A[row][c] = (A[row][c] - factor * A[col][c]) % p
        print(det % p)

main()

Step-by-Step 解説

1Toeplitz 行列の構造
$T[i][j] = a[i-j]$ なので各対角線が定数。

2行列ベクトル積 = 畳み込み
$y[i] = \sum_j a[i-j] x[j]$ は線形畳み込みの一部。FFT で $O(N \log N)$。

3Circulant 行列との関係
循環行列は DFT で対角化可能、$C = F^* \text{diag}(\text{FFT}(c)) F$。$Cx = \text{IFFT}(\text{FFT}(c) \cdot \text{FFT}(x))$。

4累乗
小問2 は行列累乗で $O(N^3 \log K)$。Toeplitz 構造を活かす高速法もあるが小 $N$ なら愚直で可。

5行列式
$\bmod p$ ガウス消去 $O(N^3)$。逆元はフェルマーの小定理 pow(a, p-2, p)。

よくあるミス

ミス	原因	正しい書き方
通常の行列積で計算	$O(N^2)$ 以上	FFT 畳み込みで $O(N \log N)$
畳み込みの添字ずれ	$a$ の添字が $-(N-1)$ から	`y[i] = conv[i+N-1]`
FFT サイズ不足	$2N-1$ の結果に余裕が必要	`size >= 2*N`
フェルマーの逆元未使用	$p$ が素数のときに有効	`pow(a, p-2, p)`

Day 032-Q4 — Toeplitz行列・Circulant行列（FFT + 効率的行列積）

問題