11.5 联测

A

发现长度 $\ge 2$ 的连续段能起到把左右两侧分开的效果。

于是需要计算若干个形如 ABABAB，ABABABA 的答案之积。

两种的答案都是 $\lceil \frac{len}{2} \rceil$。

B

暴力能做 $O(2^{2n})$。

拆一下贡献。

异或是拆不了的，考虑快速求 $f(i,j)$。

容斥，把"交集大小恰好为 $j$" 转化为"交集大小至少为 $j$"。

$g(i)$ 表示玩 $i$ 的人数（$\{a\}$ 的高位后缀和）。

$f(i,j)=\sum_{k \subset i,|k|\ge j}g(k)(-1)^{k-j}$。

式子的意义大概是枚举 $k$ 为交集，然后把 $k$ 的所有超集算进贡献，再乘容斥系数。

打完发现挂了，原来是系数中还要带一个组合数，$f(i,j)=\sum_{k \subset i,|k|\ge j}g(k)(-1)^{|k|-j}\binom{|k|}{j}$。

D

乐翻了，鉴定出原题然后不会做。甚至还写过题解。