题目链接 正解:子集和变换. 考场上只会暴力和$p=0$的情况,还只会$O(2^{n}*n^{3})$的. 然而这题题面出锅,导致考场上一直在卡裸暴力,后面的部分分没写了..听$laofu$说$O(2^{n}*n^{3})$可以过.. 所以直接讲正解.. 我们假设每个城市可以在两个不同集合,那么可以把子集卷积变成或卷积. 我们只要记下当前总共有多少个点,于是考虑设$f[i][S]$表示$i$个点,集合为$S$的方案数. 最后的$f[n][all]$就是答案,显然这个状态中的每个城市只会出现一次.