设 \(f(i,j)\) 表示 \(i\) 是否能直接或间接到达 \(j\)。
给定一个 \(n\times n\) 的矩阵 \(G\)，求满足以下条件的有向图的最小边数：
- 若 \(G_{i,j}=\mathsf{A}\)，则要求 \(f(i,j) \operatorname{and} f(j,i)=1\)。
- 若 \(G_{i,j}=\mathsf{O}\)，则要求 \(f(i,j) \operatorname{or} f(j,i)=1\)。
- 若 \(G_{i,j}=\mathsf{X}\)，则要求 \(f(i,j) \operatorname{xor} f(j,i)=1\)。
\(n\leqslant 47\)。
我们考虑每一种的限制。可以发现，A 相当于两个点在同一个强连通分量中，O 相当于两个点在同一个弱联通分量中，X 相当于两个点在同一个弱连通分量但是不在同一个强连通分量中。
不难发现，如果我们确定了每个点在哪个强连通分量中，那么最优的连边方案一定是每个强连通内部连成一个环，强连通分量之间再串成一条链（因为最后一定要形成弱联通图）。
我们注意到，如果一个点单独为一个强连通分量，其是否加入另一个强连通分量对答案没有影响；如果两个强连通分量的点数均 \(\geqslant 2\)，把它们合并可以减少一条边。于是，如果最终的图有 \(x\) 个点数 \(\geqslant 2\) 的强连通分量，则其最优方案的连边数为 \(n-1+x\)。
这样我们就需要最小化强连通分量的个数，我们首先把被 A 连接到一起的缩点，代表一定在一个强连通分量中，然后判一下无解：如果一个强连通分量中有 X 的边，则无解。
现在我们把强连通分量看成点，只关心 X 的边，那么问题就转化为了：把所有点分成若干个点集，使得点集内部没有连边，最小化点集个数。
注意到我们刚才说过大小为 \(1\) 的强连通分量怎么连都不影响答案，所以我们可以不考虑，这样新图中每个点都至少由原图中 \(2\) 个点构成，所以新图点数最大为 \(23\)。
我们考虑计算是否存在恰好分为 \(k\) 个点集的方案。设 \(f(s)\) 为点集 \(s\) 一开始是否合法，不难发现新添加一个点集是一个子集卷积的形式，则我们需要找到最小的 \(k\)，使得 \(f^k(U)\not=0\)，其中 \(U\) 是全集，乘法定义为子集卷积。显然 \(k\) 最多为 \(cnt\)（连通分量个数），这样的复杂度是 \(O(cnt^32^{cnt})\)，无法通过。
考虑优化，其实我们并不需要去做子集卷积，如果两个集合 \(S\) 和 \(T\) 有交且合法，那么显然 \(S-S\cap T\) 也是合法集合，所以我们不需要保证 \(S\cap T\) 为空。这样可以砍掉一个 \(cnt\)。
同时我们注意，我们并不需要求出所有 \(f^k(s)\)，我们只需要知道 \(f^k(U)\)，而且我们只需要一开始对 \(f\) 做一遍 FWT，每一次只需求出 \(f\) 的点值的 \(k\) 次方。而已知 FWT 后求原序列某一个值是一个子集反演的形式，我们可以在 \(O(2^{cnt})\) 的时间完成（\(f(s)=\sum\limits_{t|s=s}(-1)^{\text{popcount}(s-t)}\hat f(t)\)）。这样不算求 \(f\) 的时间，我们把时间优化到了 \(O(cnt2^{cnt})\)。
考虑怎么求 \(f\)，若 \(f(s)\) 合法，则 \(f(s-\text{lowbit}(s))\) 也一定合法，故我们只需要从 \(f(s-\text{lowbit}(s))\) 转移过来即可，需要判断 \(s-\text{lowbit}(s)\) 中是否有元素向新加入的元素有连边，这个可以在算 \(f\) 的时候顺便求出来（新添加一个元素就或以下），这样的复杂度也是 \(O(cnt2^{cnt})\) 的，详情可以看代码。
代码：
1 |
|