問題
長さ $2^N$ の数列 $A$ に対して上位ゼータ変換 $B[i] = \sum_{j \supseteq i} A[j]$ を求めよ。
制約
$1 \le N \le 20$
$0 \le A[i] \le 10^9$
入出力例
入力例 1
3
1 2 3 4 5 6 7 8出力例 1
36 20 22 12 26 14 15 8ヒント (段階的開示)
ヒント1: 方向性
愚直 $O(4^N)$ は不可能。高速ゼータ変換で $O(N \cdot 2^N)$。
ヒント2: アプローチ
各ビットについて、そのビットを持つ集合の値を、そのビットを除いた集合に足す。
ヒント3: 誘導
for bit in range(N):
for mask in range(1 << N):
if mask >> bit & 1:
B[mask ^ (1 << bit)] += B[mask]模範解答 (Python)
import sys
input = sys.stdin.readline
def upper_zeta_transform(A, N):
B = A[:]
for bit in range(N):
for mask in range(1 << N):
if (mask >> bit) & 1:
B[mask ^ (1 << bit)] += B[mask]
return B
def lower_zeta_transform(A, N):
B = A[:]
for bit in range(N):
for mask in range(1 << N):
if not ((mask >> bit) & 1):
B[mask | (1 << bit)] += B[mask]
return B
def upper_mobius_transform(B, N):
A = B[:]
for bit in range(N):
for mask in range(1 << N):
if (mask >> bit) & 1:
A[mask ^ (1 << bit)] -= A[mask]
return A
def solve():
N = int(input())
A = list(map(int, input().split()))
B = upper_zeta_transform(A, N)
print(*B)
solve()Step-by-Step 解説
1愚直 $O(4^N)$ の問題
$N=20$ で $4^{20} = 10^{12}$ → TLE。
$N=20$ で $4^{20} = 10^{12}$ → TLE。
2高速化の核心
ビット包含関係を1ビットずつ独立に処理。
ビット包含関係を1ビットずつ独立に処理。
3DP の実行順
$N \cdot 2^N \approx 2 \times 10^7$ で十分速い。
$N \cdot 2^N \approx 2 \times 10^7$ で十分速い。
4Möbius変換
ゼータの逆変換。累積加算を引き算に変えるだけ。
ゼータの逆変換。累積加算を引き算に変えるだけ。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 上位と下位の変換を混同 | bit 設定/非設定の向きミス | 上位: bit立ちから除いた集合に加算 |
| Möbius で加算 | 逆変換なのに足す | 減算に変える |
| 計算量誤解 | $O(4^N)$ と思う | 各ビット独立 → $O(N \cdot 2^N)$ |
次のステップ
- 発展問題: XOR 畳み込み（高速アダマール変換）
- 応用: bitDP + ゼータ変換