Day 034-Q4 | FFT見せかけの代数的観察

問題

長さ $N$ の整数列 $A$ と長さ $M$ の整数列 $B$。以下の $Q$ 個のクエリに答えよ。

conv l r $A[l..r]$ と $B$ の畳み込み $C$ の 全要素の和 を mod $10^9+7$ で出力
update i x $A_i$ を $x$ に更新

ここで $C_k = \sum_{i+j=k} A_{l+i} \cdot B_j$。

制約

$1 \le N, M, Q \le 10^5$

$0 \le A_i, B_j, x \le 10^9$

$0 \le l \le r < N$

$0 \le i < N$

入出力例

入力例

4 3
1 2 3 4
1 2 3
3
conv 0 3
update 1 5
conv 1 2

計算

$C = [1,4,10,16,17,12]$ (畳み込み)
$\sum C = 60$ ↔ $(1+2+3+4)\cdot(1+2+3) = 10 \cdot 6 = 60$ ✓

★ 核心の観察: FFT は不要

畳み込みの全要素の和は分配法則で展開できる:

$$\sum_k C_k = \sum_k \sum_{i+j=k} A_{l+i} B_j = \sum_i \sum_j A_{l+i} B_j = \left(\sum_i A_{l+i}\right) \cdot \left(\sum_j B_j\right)$$

結論: 問題は $A[l..r]$ の区間和 × $B$ の全体和だけで解ける。

概念図: 畳み込み和の分配

$2\times 2$ の格子で考えるとわかりやすい。$A=[a_1, a_2], B=[b_1, b_2]$ の場合:

電卓デモ: $\sum A \times \sum B$

$A$ (カンマ区切り): $B$ (カンマ区切り): 区間 $l$: $r$:

結果: --

ヒント (段階的開示)

ヒント1: 方向性

畳み込みの全要素の和は (ΣA) × (ΣB) に等しい。FFT は不要。

ヒント2: アプローチ

$B$ の全体和は最初に一度だけ計算。$A$ の区間和は BIT で動的管理 ($O(\log N)$ 更新/クエリ)。

ヒント3: 擬似コード

sum_B = sum(B) % MOD
bit = BIT(N)
for i in range(N): bit.add(i, A[i])
for query in queries:
    if update i x: bit.add(i, x - A[i]); A[i] = x
    else: print(bit.range_sum(l, r) * sum_B % MOD)

模範解答 (Python)

import sys
from sys import stdin

def main():
    MOD = 10**9 + 7
    data = stdin.buffer.read().split()
    idx = 0

    N, M = int(data[idx]), int(data[idx+1]); idx += 2
    A = [int(data[idx+i]) for i in range(N)]; idx += N
    B = [int(data[idx+i]) for i in range(M)]; idx += M
    Q = int(data[idx]); idx += 1

    sum_B = sum(B) % MOD

    # BIT (Fenwick Tree)
    bit = [0] * (N + 1)

    def bit_add(i, v):
        i += 1
        while i <= N:
            bit[i] = (bit[i] + v) % MOD
            i += i & -i

    def bit_sum(i):
        i += 1
        res = 0
        while i > 0:
            res = (res + bit[i]) % MOD
            i -= i & -i
        return res

    def range_sum(l, r):
        if l == 0:
            return bit_sum(r)
        return (bit_sum(r) - bit_sum(l-1) + MOD) % MOD

    for i in range(N):
        bit_add(i, A[i] % MOD)

    out = []
    for _ in range(Q):
        op = data[idx].decode(); idx += 1
        if op == 'update':
            i, x = int(data[idx]), int(data[idx+1]); idx += 2
            diff = (x - A[i]) % MOD
            bit_add(i, diff)
            A[i] = x
        else:
            l, r = int(data[idx]), int(data[idx+1]); idx += 2
            sa = range_sum(l, r)
            out.append(str(sa * sum_B % MOD))

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

main()

Step-by-Step 解説

1核心的観察
$\sum_k C_k = \sum_i \sum_j A_{l+i} B_j = (\sum A) \cdot (\sum B)$。掛け算の分配法則からの自明な等式。

2BIT による動的区間和
点更新 + 区間和クエリを $O(\log N)$ で。diff = x - A[i] を BIT に加算。

3クエリ処理
conv l r は range_sum(l, r) * sum_B % MOD を返すだけ。

4教訓
「畳み込み = FFT」という先入観に注意。まず代数的観察で単純化できないか確認する。

計算量

前処理: $O(N \log N + M)$
各クエリ: $O(\log N)$
合計: $O((N + Q) \log N)$ ← 余裕で 1 秒以内

よくあるミス

ミス	原因	正しい書き方
FFT を実装しようとする	畳み込み=FFT という先入観	$\sum(A*B) = \sum A \cdot \sum B$ の恒等式
mod の扱い漏れ	BIT 加算時に mod なし	`(bit[i] + v) % MOD`
update 後の `A[i]` 更新忘れ	diff 計算に古い値が必要	`diff = x - A[i]` → `A[i] = x`
prefix sum 静的	update 後の再計算	BIT で動的管理

次のステップ

発展: クエリが「$A[l..r] * B[s..t]$ の特定係数 $C_k$」の場合 → 真に FFT が必要
応用: $\prod_{i=l}^{r}(x - A_i)$ の係数クエリ → Segment Tree of Polynomials

自己評価

完全理解おおむね理解要復習

Day 034-Q4 — 高速フーリエ変換応用 (代数的観察で FFT 不要)

問題

制約