【题解】 洛谷P3694 邦邦的大合唱站队

发现尽管 \(n\) 比较大，但 \(m\) 非常小，于是考虑状压。

记 \(dp_{i}\) 表示满足条件的乐队集合为 \(i\) 时的最小出队人数，\(dp_i=\min\{dp_{i\ \ xor\ \ 1<<k}\}+w_{i\ \ xor\ \ 1<<k,k}\)，其中 \(w_{i,j}\) 表示当前状态为 \(i\) 时 \(j\) 对应的区间内未归位的人数。

用 \(sum_i\) 表示队伍 \(i\) 的人数。

预处理 \(w_{i,j}\)，先记录前缀和数组 \(s_{i,j}\) 代表前 \(i\) 人里，属于 \(j\) 乐队的人数，那么 \(w_{i,j}=sum_i-s_{i,j}\)。