FWHT / XOR Convolution / Subset Convolution Ladder

This lane is for when SOS DP already feels natural and the next step is to combine two full mask functions instead of sweeping one array.

It stays intentionally narrow:

• exact starter = xor convolution via FWHT
• flagship rep = one official verifier where the whole task is exactly that
• subset convolution stays as the stretch sibling after the first route is trusted

Who This Is For

Use this lane if:

• Bitmask DP already feels ordinary
• SOS DP no longer feels magical
• you can already think of a mask array as a function on the full boolean cube

Warm-Up

• say why xor convolution is not subset zeta
• say why xor convolution is not additive-index FFT / NTT
• recognize when the array size 2^bits is the real contract, not just an implementation detail

Warm-up compare points:

• SOS DP
• FFT / NTT

Core

• Walsh-Hadamard xor butterfly
• inverse normalization by inv(2^bits)
• exact flagship rep: Bitwise XOR Convolution

Target skill:

• see one full-cube xor-pair-combine problem and jump straight to FWHT

Stretch

• subset convolution by popcount layers plus zeta / inverse-zeta
• official stretch verifier: Library Checker - Subset Convolution

Target skill:

• know why subset convolution still belongs to this family while requiring a stronger layered route than the xor starter

Retrieval Layer

• exact quick sheet -> FWHT / XOR Convolution / Subset Convolution hot sheet
• exact starter -> fwht-xor-convolution.cpp
• parent chooser -> DP cheatsheet
• compare point -> SOS DP

External Practice

• Library Checker - Bitwise XOR Convolution
• Library Checker - Subset Convolution

Tutorial Link

• FWHT / XOR Convolution / Subset Convolution