题解：AT_fps_24_w 閉路

Lynette_lovely · 2025-11-17 11:15:02 · 题解

W - Cycle

首先考虑点双计数。

肯定要考虑容斥，但是我们不太好钦定割点集合。

考虑钦定最小割点。

设 F_{i, S} 表示 S 导出子图内，点连通并且没有 \le i 的割点的方案数。初始 F_{0, S} 为 S 连通的方案数。若钦定 i 为割点，则删除它后至少裂成两个连通块，相当于做一个集合幂级数的 \exp。另一个方面，也可以看做去除能分裂的方案，相当于求 \ln。

以及一些常数优化：由于只有一项的变化，不需要整体重做 FWT，可以根据原来 FWT 的结果算。

边双计数也可以用类似方法。

回到原题，我们先钦定 2 \sim n - 1 的点都不是割点，然后钦定 2 \sim n - 1 的点满足裂开形成的连通块要么同时包含 1, n 要么同时不包含，即求 \exp。

时间复杂度 O(2^n n^3) 或 O(3^n n)。