問題
長さ $N$（$N = 2^k$）の非負整数配列 $A$ と $B$ が与えられる。以下の4種類の畳み込みをそれぞれ計算せよ：
- OR 畳み込み: $C_i = \sum_{j \mid l = i} A_j \cdot B_l$
- AND 畳み込み: $D_i = \sum_{j \mathbin{\&} l = i} A_j \cdot B_l$
- XOR 畳み込み: $E_i = \sum_{j \oplus l = i} A_j \cdot B_l$
- GCD 畳み込み: $F_i = \sum_{\gcd(j,l) = i} A_j \cdot B_l$（$A, B$ のインデックスは $1 \le i \le M$）
各結果配列の全要素の和を $10^9 + 7$ で割った余りで出力せよ。
制約
| パラメータ | 範囲 |
|---|---|
| $N$ | $N = 2^k$, $1 \le k \le 20$ |
| $M$ | $1 \le M \le 10^6$ |
| $A_i, B_i$ | $0 \le A_i, B_i \le 10^9$ |
入出力例
入力例 1
4 6
0 1 2 3
3 2 1 0
1 2 3 4 5 6
6 5 4 3 2 1出力例 1
20 ← OR畳み込み和
20 ← AND畳み込み和
20 ← XOR畳み込み和
[GCD畳み込み和]概念図: 4種類の畳み込みの統一的な構造
ヒント（段階的開示）
ヒント1: OR 畳み込みの変換
上位ゼータ変換: $\hat{A}[S] = \sum_{T \supseteq S} A[T]$。各ビット位置 $i$ で「ビット $i$ が立っていないセル $j$ に、$j | (1 \ll i)$ のセルの値を加算」する操作を $k$ 回（$N = 2^k$）繰り返す。逆変換はその加算を減算に変えたもの。
ヒント2: XOR 畳み込み（Walsh-Hadamard）
$\hat{A}[S] = \sum_T (-1)^{\text{popcount}(S \& T)} A[T]$。バタフライ演算で $O(N \log N)$ で計算。各ステップで $(x, y) \to (x+y, x-y)$ を適用。逆変換は同じ変換後に $N$ で割る。
ヒント3: GCD 畳み込みのコード骨格
# Dirichlet zeta: g[d] = sum_{d|n} f[n]
for d in range(1, M+1):
for n in range(2*d, M+1, d):
g[d] += f[n]
# 点積後の Dirichlet Mobius 逆変換
for d in range(1, M+1):
for n in range(2*d, M+1, d):
g[d] -= g[n] # 差分でメビウス逆変換模範解答 (Python)
import sys
input = sys.stdin.readline
MOD = 10**9 + 7
def solve():
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = [0] + list(map(int, input().split())) # 1-indexed
D = [0] + list(map(int, input().split())) # 1-indexed
k = N.bit_length() - 1
def zeta_or(f):
for i in range(k):
for j in range(N):
if not (j >> i & 1):
f[j] = (f[j] + f[j | (1 << i)]) % MOD
def mobius_or(f):
for i in range(k):
for j in range(N):
if not (j >> i & 1):
f[j] = (f[j] - f[j | (1 << i)]) % MOD
def zeta_and(f):
for i in range(k):
for j in range(N):
if j >> i & 1:
f[j] = (f[j] + f[j ^ (1 << i)]) % MOD
def mobius_and(f):
for i in range(k):
for j in range(N):
if j >> i & 1:
f[j] = (f[j] - f[j ^ (1 << i)]) % MOD
def fwht(f):
h = 1
while h < N:
for j in range(0, N, h * 2):
for l in range(j, j + h):
x, y = f[l], f[l + h]
f[l] = (x + y) % MOD
f[l + h] = (x - y) % MOD
h *= 2
def ifwht(f):
fwht(f)
invN = pow(N, MOD - 2, MOD)
for i in range(N):
f[i] = f[i] * invN % MOD
# OR convolution
fa, fb = A[:], B[:]
zeta_or(fa); zeta_or(fb)
fc_or = [(fa[i] * fb[i]) % MOD for i in range(N)]
mobius_or(fc_or)
ans_or = sum(fc_or) % MOD
# AND convolution
fa, fb = A[:], B[:]
zeta_and(fa); zeta_and(fb)
fc_and = [(fa[i] * fb[i]) % MOD for i in range(N)]
mobius_and(fc_and)
ans_and = sum(fc_and) % MOD
# XOR convolution (Walsh-Hadamard)
fa, fb = A[:], B[:]
fwht(fa); fwht(fb)
fc_xor = [(fa[i] * fb[i]) % MOD for i in range(N)]
ifwht(fc_xor)
ans_xor = sum(fc_xor) % MOD
# GCD convolution (Dirichlet)
gc_hat = [0] * (M + 1)
gd_hat = [0] * (M + 1)
for d in range(1, M + 1):
for n in range(d, M + 1, d):
gc_hat[d] = (gc_hat[d] + C[n]) % MOD
gd_hat[d] = (gd_hat[d] + D[n]) % MOD
ge_hat = [(gc_hat[i] * gd_hat[i]) % MOD for i in range(M + 1)]
# Dirichlet Mobius inversion
ge = ge_hat[:]
for d in range(1, M + 1):
for n in range(2 * d, M + 1, d):
ge[d] = (ge[d] - ge[n]) % MOD
ans_gcd = sum(ge[1:]) % MOD
print(ans_or)
print(ans_and)
print(ans_xor)
print(ans_gcd)
solve()Step-by-Step 解説
Step 1: OR 畳み込み — 上位ゼータ変換
$\hat{A}[S] = \sum_{T \supseteq S} A[T]$（$S$ のスーパーセット和）を計算。各ビット位置 $i$ で「ビット $i$ が立っていないセルに、立っているセルの値を加算」する操作を $k$ 回繰り返す。逆変換（メビウス変換）は加算を減算に変えたもの。
Step 2: XOR 畳み込み — Walsh-Hadamard 変換
$\hat{A}[S] = \sum_T (-1)^{\text{popcount}(S \& T)} A[T]$。バタフライ演算 $(x, y) \to (x+y, x-y)$ で $O(N \log N)$。逆変換は同じ変換を行い $N$ で割る（自己逆変換の性質）。
Step 3: GCD 畳み込み — Dirichlet ゼータ変換
$\hat{F}[d] = \sum_{d|n} F[n]$（倍数和）。点ごとの積後にメビウス関数による逆変換（Dirichlet メビウス変換: 各 $d$ の倍数から引く）で GCD 畳み込みを得る。
Step 4: 統一的な視点
| 演算 | 変換 | 逆変換 | 計算量 |
|---|---|---|---|
| OR | 上位ゼータ | 上位メビウス | $O(N \log N)$ |
| AND | 下位ゼータ | 下位メビウス | $O(N \log N)$ |
| XOR | Walsh-Hadamard | 逆 WHT | $O(N \log N)$ |
| GCD | Dirichlet ゼータ | Dirichlet メビウス | $O(M \log M)$ |
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| OR と AND の変換方向を逆にする | 上位/下位の混同 | OR=スーパーセット（ビット立てる方向）, AND=サブセット |
| WHT の逆変換で $k$ で割る | $N = 2^k$ と $k$ の混同 | N の逆元で割る（pow(N, MOD-2, MOD)） |
GCD 畳み込みで ge[0] を含める |
インデックス 0 は未定義 | sum(ge[1:]) |
次のステップ
発展問題: LCM 畳み込み（$\sum_{\text{lcm}(j,l)=i} A_j \cdot B_l$）を GCD 畳み込みとメビウス反転を組み合わせて求めよ。また、$k$ 乗 OR 畳み込み（同じ配列の $k$ 回 OR 畳み込み）を FPS の形で表現せよ。