题解：CF2070F Friends and Pizza

· · 题解

设第 i 个人喜欢吃的蛋糕的 bitmask 为 s[i]，设所有奇数片蛋糕的 bitmask 为 D

那么能选 i,j 两个人当且仅当 s[i]\cap s[j]\cap D=0

考虑某个 bitmask k 能被哪几对 i,j 得到，即求出：

cnt[k]=\sum_{1\le i<j\le m}[s[i]\cap s[j]\cap D=0][s[i]|s[j]=k]

这是子集卷积的变形，即：

cnt[k]=\sum_{1\le i<j\le m}[(s[i]\cap D)\cap (s[j]\cap D)=0][s[i]|s[j]=k]

考察正常的子集卷积的推导方式：

i\cup j=k\\ i\cap j=0\Rightarrow |i|+|j|=|i\cup j|

因此加上一维 popcnt，内层使用 FWT 做 or 卷积即可。

那么在这里

i\cup j=k\\ i\cap j\cap D=0\Rightarrow |i\cap D|+|j\cap D|=|(i\cap D)\cup (j\cap D)|=|(i\cup j)\cap D|

于是初始化时：

a[\operatorname{popcnt}(i\cap D)][i]+=1

在取出答案时：

ans=a[\operatorname{popcnt}(i\cap D)][i]

就做完了，注意要把 i=j 的多算的部分减掉，再把答案除以二

时间复杂度 O(2^n\times n^2+\sum a_i)，空间复杂度 O(2^n\times n)