問題
長さ $2^n$ の数列 $A, B$ に対して $C_k = \sum_{i \oplus j = k} A_i B_j$ を求めよ。
制約
$1 \le n \le 18$
$0 \le a_i, b_i \le 10^9$
答えは $10^{18}$ 以内
入出力例
入力例 1
2
1 2 3 4
4 3 2 1出力例 1
26 28 18 16ヒント (段階的開示)
ヒント1: 方向性
$O(4^n)$ は不可能。FWHT で $O(n \cdot 2^n)$。
ヒント2: アプローチ
XOR-アダマール変換 → 点乗算 → 逆変換。バタフライ演算で $a' = a+b, b' = a-b$。
ヒント3: 誘導
逆変換時に $n$ で割る（整数除算が成立）。
模範解答 (Python)
import sys
input = sys.stdin.readline
def fwht(a, invert=False):
h = 1
while h < len(a):
for i in range(0, len(a), h * 2):
for j in range(i, i + h):
x, y = a[j], a[j + h]
a[j] = x + y
a[j + h] = x - y
h *= 2
if invert:
n = len(a)
a[:] = [v // n for v in a]
def xor_convolution(a, b):
fwht(a)
fwht(b)
c = [a[i] * b[i] for i in range(len(a))]
fwht(c, invert=True)
return c
def main():
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = xor_convolution(a, b)
print(*c)
main()Step-by-Step 解説
1XOR 畳み込みの意味
多項式乗算の畳み込みを XOR で置き換えたもの。
多項式乗算の畳み込みを XOR で置き換えたもの。
2アダマール変換のバタフライ
[a, b] → [a+b, a-b] を $n$ 段繰り返す。$O(n \cdot 2^n)$。
3変換 → 点積 → 逆変換
$\hat{C}_i = \hat{A}_i \cdot \hat{B}_i$ → 逆変換で $C$ を得る。
$\hat{C}_i = \hat{A}_i \cdot \hat{B}_i$ → 逆変換で $C$ を得る。
4XOR との対応
アダマール行列 $H_{ij} = (-1)^{\text{popcount}(i \& j)}$ が XOR の加法構造と合致。
アダマール行列 $H_{ij} = (-1)^{\text{popcount}(i \& j)}$ が XOR の加法構造と合致。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
逆変換で // n 忘れ | 変換で $n$ 倍になる | a[:] = [v // n for v in a] |
h = 1 から始めない | 初期化ミス | 必ず h = 1 から |
| AND/OR の変換と混用 | 変換種類間違い | XOR は $a'=a+b, b'=a-b$ |
次のステップ
- 発展問題: AND/OR 畳み込み
- 応用: サブセット和との違い