Subset Convolution¶

Boolean-cube transforms beyond plain zeta sweeps, starting with xor convolution via Walsh-Hadamard transform and stretching to subset convolution by popcount layering.

Topic slug: dp/fwht-subset-convolution
Tutorial page: Open tutorial
Ladder page: Open ladder
Repo problems currently tagged here: 1
Repo companion pages: 5
Curated external problems: 2

Microtopics¶

fwht
walsh-hadamard
xor-convolution
subset-convolution
boolean-cube-transform
popcount-layering

Learning Sources¶

Source	Type
Competitive Programmer's Handbook	`Reference`
Guide to Competitive Programming	`Reference`
Library Checker Bitwise XOR Convolution	`Practice`

Practice Sources¶

Source	Type
Library Checker Subset Convolution	`Practice`

Repo Companion Material¶

Material	Type
FWHT / XOR Convolution / Subset Convolution hot sheet	`quick reference`
Bitwise XOR Convolution note	`flagship note`
SOS DP tutorial	`compare point`
FFT / NTT tutorial	`compare point`
Template Library exact starter route	`starter route`

Curated External Problems¶

Core¶

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Bitwise XOR Convolution	`Library Checker`	`Hard`	XOR Convolution, Boolean Cube	Dynamic Programming; Algebra; Implementation	Sos DP; Modular Arithmetic; Power-Of-Two Mask Space	Walsh-Hadamard; Full Cube	The clean first verifier where the entire task is one xor convolution on the full boolean cube and the only intended route is Walsh-Hadamard transform.

Stretch¶

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Subset Convolution	`Library Checker`	`Hard`	Subset Convolution, Boolean Cube	Dynamic Programming; Algebra; Implementation	Sos DP; Popcount Layering; Modular Arithmetic	Popcount Layers; Zeta Transform; Full Cube	The natural stretch sibling where plain SOS sweeps are no longer enough and the exact subset split must be preserved through popcount-layered transforms.

Repo Problems¶

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`BITWISEXORCONVOLUTION`	Bitwise XOR Convolution	`primary`	`hard`	-	Note	Code

Regeneration¶

python3 scripts/generate_problem_catalog.py