問題
長さ $2^N$ の整数配列 $A$, $B$ が与えられる。各マスク $m$ に対して以下を求めよ。
$f(m) = \sum_{s \subseteq m} A[s]$ および $g(m) = \sum_{s : m \subseteq s} B[s]$
制約
$1 \le N \le 20$
$0 \le A_i, B_i \le 10^9$
入出力例
入力例 1
3
1 2 3 4 5 6 7 8
1 1 1 1 1 1 1 1出力例 1
f: 1 3 4 10 6 14 15 36
g: 8 4 4 2 4 2 2 1ヒント (段階的開示)
ヒント1: 方向性
愚直は $O(3^N)$ で TLE。SOS DP は $O(N \cdot 2^N)$ に改善。
ヒント2: アプローチ
$i$ ビット目に注目した DP。
dp[i][m] = m のうち、0〜i-1 ビット目だけを「下げる」ことを許した場合の部分集合和。ヒント3: 誘導
for i in range(N):
for m in range(1 << N):
if m >> i & 1:
f[m] += f[m ^ (1 << i)]模範解答 (Python)
import sys
input = sys.stdin.readline
def main():
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
f = A[:]
for i in range(N):
for m in range(1 << N):
if m >> i & 1:
f[m] += f[m ^ (1 << i)]
g = B[:]
for i in range(N):
for m in range(1 << N):
if not (m >> i & 1):
g[m] += g[m | (1 << i)]
print("f:", *f)
print("g:", *g)
main()Step-by-Step 解説
1問題の核心
$f(m) = \sum_{s \subseteq m} A[s]$。愚直は $O(3^N)$、SOS で $O(N \cdot 2^N)$。
$f(m) = \sum_{s \subseteq m} A[s]$。愚直は $O(3^N)$、SOS で $O(N \cdot 2^N)$。
2SOS DPのアイデア
「ビット $i$ を下げる」遷移を $i=0,\ldots,N-1$ の順に適用。
「ビット $i$ を下げる」遷移を $i=0,\ldots,N-1$ の順に適用。
3計算量
$N \times 2^N = 20 \times 10^6 = 2 \times 10^7$。
$N \times 2^N = 20 \times 10^6 = 2 \times 10^7$。
4Superset SOS
$g(m)$ は逆向き: ビット $i$ を「上げる」ことを許す。
$g(m)$ は逆向き: ビット $i$ を「上げる」ことを許す。
5応用例
AND畳み込み、XOR畳み込み、高速ゼータ変換。
AND畳み込み、XOR畳み込み、高速ゼータ変換。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
i と m のループ順を逆にする | 更新が正しく伝播しない | 外ループ i、内ループ m |
| supersetの条件を逆に | 逆になる | not (m >> i & 1) で下位ビット0なら上へ |
| $3^N$ 解法と結果比較を怠る | バグ気づかず提出 | N=3 等で手計算と突き合わせる |
次のステップ
- 発展: AND畳み込み $h[k] = \sum_{i \& j = k} A[i] B[j]$ を $O(N \cdot 2^N)$ で
- OR・XOR畳み込みとの統一的理解