Day 116-Q4 | OR畳み込み（Subset Zeta/Möbius変換）

問題

長さ$2^N$の数列$f,g$（添字は$0$以上$2^N$未満の整数で、$N$ビットの集合とみなす）が与えられる。次を満たす数列$h$を求めよ。

$$h[k] = \sum_{i \,\mathrm{OR}\, j = k} f[i] \cdot g[j] \pmod{998244353}$$

入力形式

N
f_0 f_1 ... f_{2^N-1}
g_0 g_1 ... g_{2^N-1}

制約

$0 \le N \le 20$

$0 \le f_i, g_i < 998244353$

入出力例

入力例1

1
1 2
3 4

出力例1

3 18

$h[0]=f_0g_0=3$。$h[1]$は$i\,\mathrm{OR}\,j=1$の$(0,1),(1,0),(1,1)$の和で$f_0g_1+f_1g_0+f_1g_1=4+6+8=18$。

概念図: Subset Zeta変換 → 積 → Möbius逆変換

ヒント（段階的開示）

ヒント1: 方向性

全ての添字ペア$(i,j)$を愚直に試すと$O(4^N)$かかり間に合わない。以前扱ったAND畳み込みでは「Superset Zeta変換（上位集合に値を伝播）」を使ったが、OR畳み込みにはその対になる「Subset Zeta変換」、いわゆるSOS（Sum over Subsets）DPを使う。

ヒント2: アプローチ

$F[S]=\sum_{T\subseteq S}f[T]$、$G[S]=\sum_{T\subseteq S}g[T]$ を計算し、要素ごとの積$H[S]=F[S]\cdot G[S]$を作ると、$H[S]=\sum_{T_1\subseteq S}\sum_{T_2\subseteq S}f[T_1]g[T_2]$になる。「$T_1\subseteq S$かつ$T_2\subseteq S$」という条件は「$T_1\,\mathrm{OR}\,T_2\subseteq S$」と同値である。ここから逆メビウス変換（包除原理）を$H$に施すことで、ちょうど$T_1\,\mathrm{OR}\,T_2=S$となる項だけを取り出せる。

ヒント3: 誘導（コード骨格）

for bit in range(N):
    for mask in range(1 << N):
        if mask & (1 << bit):
            F[mask] += F[mask ^ (1 << bit)]   # Subset Zeta変換（SOS）
# H = F * G （要素ごとの積）
for bit in range(N):
    for mask in range(1 << N):
        if mask & (1 << bit):
            H[mask] -= H[mask ^ (1 << bit)]   # 逆変換（Möbius）

模範解答 (Python)

import sys


def solve():
    data = sys.stdin.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    size = 1 << N
    f = [int(data[idx + i]) for i in range(size)]; idx += size
    g = [int(data[idx + i]) for i in range(size)]; idx += size
    MOD = 998244353

    F = f[:]
    G = g[:]
    for bit in range(N):
        b = 1 << bit
        for mask in range(size):
            if mask & b:
                F[mask] = (F[mask] + F[mask ^ b]) % MOD
                G[mask] = (G[mask] + G[mask ^ b]) % MOD

    H = [(F[mask] * G[mask]) % MOD for mask in range(size)]

    for bit in range(N):
        b = 1 << bit
        for mask in range(size):
            if mask & b:
                H[mask] = (H[mask] - H[mask ^ b]) % MOD

    print(' '.join(str(h % MOD) for h in H))


solve()

計算量: Subset Zeta変換・逆変換ともに$O(2^N N)$。全体で$O(2^N N)$。ランダム200ケースで、愚直な$O(4^N)$畳み込みと全出力一致を確認済み。

Step-by-Step 解説

1Subset Zeta変換（SOS DP）の意味
各ビットについて「そのビットが立っているマスクは、そのビットを落としたマスクの値を足し込む」を$N$回繰り返すことで、$F[S]=\sum_{T\subseteq S}f[T]$が計算できる。1ビットずつ処理することで依存関係が壊れず全体$O(2^N N)$。

2点ごとの積が意味すること
$F[S]G[S]$は「$S$の部分集合同士の畳み込みの累積和」になっている。全ての$S$について計算すれば、あとは差分を取るだけで$T_1\,\mathrm{OR}\,T_2=S$ぴったりの項を復元できる。

3逆変換（Möbius変換）で厳密な値を復元
Zeta変換の逆操作を行うことで「$S$の部分集合の総和」から「ちょうど$S$の値」を引き算的に取り出す。ループの形はほぼ同じで+=が-=に変わるだけ。

4MOD演算のタイミング
各更新のたびに% MODを取る。Pythonの%は常に非負を返すが、意識せず書くとバグの温床になりやすい。

5AND畳み込みとの対比
AND畳み込みは「上位集合（superset）への伝播」、OR畳み込みは「下位集合（subset）からの集約」で、変換の向きがちょうど逆になっている。

よくあるミス

ミス	原因	正しい書き方
ビットのループとmaskのループの順序関係を誤解し、正しくSOS DPが機能しない	DPの依存関係（1ビットずつ全maskを処理し終えてから次のビットへ）を理解していない	各ビットについて全mask走査を完了してから次のビットに進む二重ループを守る
AND畳み込み（Superset Zeta）とOR畳み込み（Subset Zeta）の変換方向を混同する	「上位集合へ足す」か「下位集合の情報を集める」かの違いを取り違える	OR畳み込みは`mask & (1<が真の側に部分集合の値を足し込む（Subset Zeta）。AND畳み込みは逆（Superset Zeta）`
逆変換（Möbius）の後、負の剰余のまま出力してしまう	他言語での剰余演算の癖が抜けない	Pythonの`%`は非負を返すが、最終出力前に`% MOD`を確実にかけて明示する
$N=0$（要素数1）の境界ケースで結果が正しいか確認していない	境界値のテストを怠る	$N=0$の場合、$h[0]=f[0]\cdot g[0]$になることを手計算で確認する

次のステップ

発展: XOR畳み込み（Walsh-Hadamard変換）との実装・計算量の違いを比較する
発展: AND畳み込みとOR畳み込みを組み合わせ、集合演算を含む複合クエリを解く

自己評価

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

Day 116-Q4 — OR畳み込み（Subset Zeta/Möbius変換によるOR Convolution O(2^N N)）

問題