P5188 PALACINKE 题解

我不会啊。

首先观察一下题目描述。

“采购方式包含了她经过的结点的次序，以及她在每条路上买不买材料，但不计她在哪个商店买了什么”。

发现等价于满足“进去买东西的点的并集恰好等于全集”的方案个数。

显然直接求需要一个状压，并不是很优秀。

但是我们发现，“进去买东西的点的并集等于某个集合的子集”的答案是好求的，你只需要只在是子集的边上买东西即可，其它边只通过。

不妨另 表示走了 步，目前在点 。另 表示原图中的边， 表示是子集的边，转移就是

很大，但是我们可以使用矩阵快速幂来快速计算。

接下来是通过子集的答案算出全集的答案，此方法在小星星亦有记载，其实就是子集反演。

另 表示进去买东西的点的并集恰好为 的方案数， 表示为 的子集的方案数。

有

我们希望求出一组数 满足

只有一组方程咋解啊？

不妨拆到每个元素上。这样我们就有 组方程，可以高斯消元求解。

我们也可以继续观察，注意到每个元素 只在 的超集有贡献，而我们希望 有贡献当且仅当 。除了 ，每个子集都有 个超集。我们让其中一部分做 的贡献，另一部分做 的贡献就可以抵消掉了。

因而容斥系数 。