問題
$2^n$ 個の整数からなる数列 $f_0, f_1, \dots, f_{2^n-1}$ と $g_0, g_1, \dots, g_{2^n-1}$ が与えられる（添字はビット列とみなす）。
次の AND畳み込み を計算せよ。 $$ h_x = \sum_{i \,\&\, j = x} f_i \cdot g_j \pmod{998244353} $$ $h_0, h_1, \dots, h_{2^n-1}$ を空白区切りで出力せよ。
入力形式
n
f_0 f_1 ... f_{2^n-1}
g_0 g_1 ... g_{2^n-1}制約
$1 \le n \le 20$
$0 \le f_i, g_i < 998244353$
入出力例
入力例1
2
1 2 3 4
5 6 7 8出力例1
103 52 73 32例えば$h_3$（$x=11_2$）は$i\&j=3$となる$(i,j)$、つまり$i=j=3$の1通りのみで$f_3g_3=4\times8=32$。$h_2$（$x=10_2$）は$i\&j=2$となる組$(2,2),(2,3),(3,2)$の3通りで$21+24+28=73$。全体の和は$\sum h_x=(\sum f_i)(\sum g_j)=10\times26=260$で検算できる。
概念図: 上位集合和（Superset Sum）でANDを畳み込む
ヒント（段階的開示）
ヒント1: 方向性
OR畳み込み（$i\mid j=x$）は「部分集合和」の高速ゼータ変換（SOS DP）で解けることが知られている。AND畳み込みはその双対で、「上位集合和（superset sum）」の高速ゼータ変換を使う。
ヒント2: アプローチ
$\zeta^{\supseteq}(f)[x] = \sum_{y \supseteq x} f_y$ を定義する。各ビット $b$ について、$x$ のビット $b$ が $0$ のとき $f[x] \mathrel{+}= f[x | (1<
ヒント3: 誘導（コード骨格）
def superset_zeta(a, n):
for b in range(n):
for x in range(1 << n):
if not (x >> b) & 1:
a[x] = (a[x] + a[x | (1 << b)]) % MOD
def superset_mobius(a, n):
for b in range(n):
for x in range(1 << n):
if not (x >> b) & 1:
a[x] = (a[x] - a[x | (1 << b)]) % MOD
# F = superset_zeta(f); G = superset_zeta(g)
# H[x] = F[x] * G[x] (pointwise)
# h = superset_mobius(H)模範解答 (Python)
import sys
MOD = 998244353
def main():
data = sys.stdin.buffer.read().split()
idx = 0
n = int(data[idx]); idx += 1
size = 1 << n
f = [int(data[idx + i]) % MOD for i in range(size)]; idx += size
g = [int(data[idx + i]) % MOD for i in range(size)]; idx += size
def superset_zeta(a):
for b in range(n):
bit = 1 << b
for x in range(size):
if not (x & bit):
a[x] = (a[x] + a[x | bit]) % MOD
def superset_mobius(a):
for b in range(n):
bit = 1 << b
for x in range(size):
if not (x & bit):
a[x] = (a[x] - a[x | bit]) % MOD
F = f[:]
G = g[:]
superset_zeta(F)
superset_zeta(G)
H = [(F[x] * G[x]) % MOD for x in range(size)]
superset_mobius(H)
print(" ".join(str(v % MOD) for v in H))
main()計算量: ゼータ変換・メビウス変換ともに $O(2^n \cdot n)$。$n=20$ で $2^{20}\times20 \approx 2\times10^7$ 回の演算を3回。ブルートフォース $O(4^n)$（$n\le10$程度）との一致を確認済み（例1のブルートフォース値と模範解答の出力103 52 73 32が完全一致）。
Step-by-Step 解説
1OR畳み込みとの対比で理解する
OR畳み込みは「部分集合和」$\hat f[x]=\sum_{y\subseteq x}f_y$を使う。AND畳み込みはこれの双対で「上位集合和」を使い、更新の向きが逆になる。
OR畳み込みは「部分集合和」$\hat f[x]=\sum_{y\subseteq x}f_y$を使う。AND畳み込みはこれの双対で「上位集合和」を使い、更新の向きが逆になる。
2上位集合和ゼータ変換の意味
$\zeta^{\supseteq}(f)[x]=\sum_{y\supseteq x}f_y$は「$x$を部分集合として含むすべての$y$」の和。各ビットについて独立に更新すれば計算できる。
$\zeta^{\supseteq}(f)[x]=\sum_{y\supseteq x}f_y$は「$x$を部分集合として含むすべての$y$」の和。各ビットについて独立に更新すれば計算できる。
3なぜ点ごとの積が畳み込みになるのか
$\zeta^{\supseteq}(f)[x]\cdot\zeta^{\supseteq}(g)[x]=\sum_{i\supseteq x}\sum_{j\supseteq x}f_ig_j$。これを$x$についてメビウス変換すると、$i\&j=x$の組だけが残る。
$\zeta^{\supseteq}(f)[x]\cdot\zeta^{\supseteq}(g)[x]=\sum_{i\supseteq x}\sum_{j\supseteq x}f_ig_j$。これを$x$についてメビウス変換すると、$i\&j=x$の組だけが残る。
4メビウス変換は差分を取るだけ
ゼータ変換の逆操作は、同じループ構造で加算を減算に変えるだけで実現できる。
ゼータ変換の逆操作は、同じループ構造で加算を減算に変えるだけで実現できる。
5MODと負の値の扱い
メビウス変換では引き算が発生し途中で負の値になりうる。Pythonの
メビウス変換では引き算が発生し途中で負の値になりうる。Pythonの
%は負数でも正の余りを返すが、他言語では+MODしてから%MODする必要がある。よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| OR畳み込みと同じ更新方向（部分集合和）を使ってしまう | SOS DPのコードをそのまま流用する | AND畳み込みは「ビットが立っていない側に、立っている側の値を足す」逆方向の更新を使う |
ゼータ変換前にf,gを直接書き換えて元の配列を破壊する | インプレース更新の副作用を考慮しない | f[:]でコピーしてから変換する |
| ビット$b$のループと$x$のループの順序を間違える | 「ビットごとに全体を1回走査する」構造を理解していない | 外側をビット$b$、内側を$x$の全走査にする |
| $n$が大きいときPythonのループが遅くて間に合わない | 純粋なPythonループの定数倍を過小評価する | NumPyのベクトル化やarrayモジュールでの実装を検討する |
次のステップ
- 発展: XOR畳み込み（Walsh-Hadamard変換、Day059 Q1）・OR畳み込み（Day020 Q2）とAND畳み込みを統一的に理解し、3つの違いを一覧化する
- 発展: 「AND畳み込みを$k$回繰り返した結果」を高速に求める（ゼータ変換した状態で$k$乗してから1回だけ逆変換すればよい）
- 発展: 部分集合の要素数制約を持つ本来のSubset Convolutionとの違いを整理する