接下来有一道题目，和我对这个题目给出的分析，已经用你同级别的SOTA模型检验过是正确的，你需要结合我...

Question

接下来有一道题目，和我对这个题目给出的分析，已经用你同级别的SOTA模型检验过是正确的，你需要结合我对这个题的解法，解决最后一部分复杂连通块内的计数(大概率是DP)问题。

题目：

给定正整数 $n\ (1 \leq n \leq 2 \times 10^5)$ 和两个长度为 $n$ 的序列 $a,b$ ，确保 $a_i \neq b_i$ 并且 $1 \leq a_i, b_i \leq n$ 。你需要对合法 $n$ 阶排列 $p$ 计数，一个 $n$ 阶排列 $p$ 是合法的，当且仅当 $\forall 1 \leq i \leq n, p_i \ne a_i \wedge p_i \ne b_i$ 。答案对 $2^{32}$ 取模。

做法：

设 $c_k$ 表示钦定 $k$ 个位置不合法(即 $p_i = a_i$ 或 $p_i = b_i$ )，并且这 $k$ 个不合法位置对应的值域不冲突（依旧成一个排列）的方案数，那么简单容斥一下得到最终答案为 $\sum_{k=0}^{n} (-1)^k c_k \times (n - k)!$ 。

接下来考虑求 $c_k$ 的问题，可以视作特殊的二分图匹配计数状物：

左部点为位置 $1, 2, \dots, n$ ，右部点为数值 $1, 2, \dots, n$ 。
对任意一个位置 $1 \leq i \leq n$ ，链接 $(i, a_i)$ 和 $(i, b_i)$ 。
$c_k$ 等价于在这个二分图中选出 $k$ 条边，使得其边诱导子图成一个匹配的方案数。

因为 $a, b$ 均为排列，所以上述二分图中每个点度数均严格为 $2$ ，这必定可以分解为若干个不交的环。可以直接对每个连通分量 DFS 找环。环与环在原计数问题对应的代数簇上是正交的所以只需要分别考虑每一个环。

对每一个环，只需要考虑写出它取 $k$ 条边的匹配对应的生成函数，记为 $P_{L}(x)$ ，其中 $L$ 为环长， $x$ 为选取的边的数量。 $L = 1$ 时有且仅有 $P_{1}(x) = (1 + x)$ ，其实因为 $a_i = b_i$ 不存在所以这个我们无需考虑。对 $L \geq 2$ 时我们有 $P_{L}(x) = \frac{2L}{2L - k} \times \binom{2L - k}{k} = 1 + \sum_{k = 1}^{L} x^k \times \left (\binom{2L - k}{k} + \binom{2L-k-1}{k-1} \right )$ ，这个不难用组合恒等式或者格路计数的思路解出。

得到每个环对应的生成函数后，所求即为 $[x^k]\prod_{C \in G} P_{|C|}(x)$ 。可以 $\mathcal{O}(n^2)$ 计算，使用 NTT 优化不难做到 $\mathcal{O}(n \log n)$ ，模数是 $2^{32}$ 换成 MTT 对质因子做再复合即可。其实这个地方是一个伏笔，你注意到 UOJ 不太可能出这种纯粹为了为难你设置的算法。

然后考虑原问题，即 $a,b$ 限制仅为值域不超过 $n$ 的整数序列，如果直接看图论建模结果会发现这个东西是 NP 的，很难处理，但是你可以注意到（花我快两天）首先左侧任何一个点的度数仍然只有 $2$ ，模数又是 $2^{32}$ ，又是生成函数卷积形式，这提醒了我们！对于答案 $\sum_{k=0}^{n} (-1)^k c_k (n - k)! \pmod {2^{32}}$ ，由勒让德定理我们知道 $m!$ 中至多包含 $m - \text{popcount}(m)$ 个 $2$ 质因子，所以如果 $m \geq 34$ 那么这一项对最终答案的贡献是 $0$ ，不需要计算！也即我们只需要求出 $c_k \ (n - 33 \leq k \leq n)$ 即可。

再来考虑如何求这些项，首先和上面特殊性质类似的还是建出右部点内部的图 $G$ ，那么原始二分图中选 $k$ 条边等价于在 $G$ 中选取 $k$ 条边对应的匹配。如果能做到那么这 $k$ 条边的边诱导子图必定是一个基环树，证明考虑对树黑白染色即可。并且大小为 $k$ 的匹配数 $c_k$ 等于所有基环树的权重之和。即：

c_k = \sum\limits_{\substack{F \subseteq G \\ |E(F)| = k \\ F \text{ is a pseudoforest}}} {{\prod\limits_{C \in F}} W(C)}

如果 $C$ 是树那么权值就是 $W(C) = |V(C)|$ ，即节点数，因为唯一的非目标点可以任选。

否则 $C$ 是环或基环树那么 $W(C) = 2$ ，对应两种定向方向。

又因为图恰有 $n$ 个点和 $n$ 条边，所以对于 $G$ 的任意连通块，令 $D_{C} = |E_{C}| - |V_{C}|$ ，则必定有 $\sum_{C} D_C = 0$ 。记 $t$ 为图中树连通块，即 $D_C = -1$ 的数目，必定有 $\sum_{D_C \gt 0} D_C = t$ 。此时我们需要从 $G$ 中删去 $m = n - k \leq 33$ 使其变为基环树。则必定要删去 $m \geq t$ 条边才能删出树来，故只有 $m \geq t$ 才能选出基环树。又因为只需要考虑 $m \leq 33$ 的情形，所以如果 $t \gt 33$ 那么所有 $c_k$ 均为 $0$ 了，这进一步简化了要求的东西！

因为 $t$ 是常数级别的，所以可以直接将问题转化为类似于，对着从 $G$ 中删去 $t$ 条边的过程计数的问题。刻画这东西的生成函数：

对于树的情形可以直接 DP，令 $f(u,k,0/1)$ 表示以 $u$ 为根子树，扔掉 $k$ 条边后当前 $u$ 所在分量内是否已经选定那个起始点的方案数。合并直接树上背包，复杂度 $\mathcal{O}(m^2 \times |V(G)|)$ 。
对于基环树（包括退化为环），可以直接在环上任取一条边，对它两个方向断开的方案分别计数，退化为做两遍树的情形。
对于复杂连通块，这个我还不会，我现在只会一个基于非树边的 $\mathcal{O}(n \times 2^x)$ 做法，其中 $x$ 为非树边数目，这个东西在最坏情况下肯定是过不了的，请你给一些能严格计算论证可过的做法。

Answer 1

你最后这个“复杂连通块”不用按非树边 $2^x$ 枚举。关键换一个计数视角：

不要再显式维护“这个分量是不是树 / 基环树”。
直接数“每条保留边选择一个端点，且每个点最多被选择一次”的方案。

这正好就是原二分图匹配计数；而且它天然等价于你前面写的权值：

树分量：边数 $=|V|-1$ ，每个点最多被选一次，所以恰好有一个点没被选，未选点可任选，权值 $=|V|$ ；
基环树分量：边数 $=|V|$ ，所有点都被选，环上只有两个方向，权值 $=2$ ；
多环分量：边数 $>|V|$ ，不可能每条边都选一个互不冲突的端点，所以自动为 $0$ 。

所以复杂块内只需要做一个局部容量 DP：每个点容量为 1，每条边有三种选择：

\text{删掉},\quad \text{选左端点},\quad \text{选右端点}.

这样就不需要维护连通性、环数、根、方向，复杂度会低很多。

1. 对每个连通块求多项式

对原图 $G$ 的每个连通块 $H$ ，求

F_H(y)=\sum_{r=0}^{33} f_H[r]y^r

其中 $f_H[r]$ 表示：在 $H$ 中删掉 $r$ 条边，其余边各自选择一个端点，并且每个点最多被选择一次的方案数。

最后把所有连通块的 $F_H$ 卷起来：

C[m]=[y^m]\prod_H F_H(y),

则

c_{n-m}=C[m].

最终答案是

\text{Ans} = \sum_{m=0}^{33} (-1)^{n-m} C[m]\cdot m! \pmod {2^{32}}.

因为 $m\ge 34$ 时

v_2(m!)=m-\operatorname{popcount}(m)\ge 32,

所以这些项全是 $0$ 。

2. 复杂连通块的 DP 状态

对复杂连通块 $H$ ，令

q=|E_H|-|V_H|+1.

由于前面已经有

\sum_{D_C>0}D_C=t\le 33,

所以复杂连通块满足

q=D_H+1\le 34.

这说明它的反馈边数很小，可以做小树宽 DP。

对 $H$ 做一个 tree decomposition。复杂块的树宽由反馈边数控制，可以用标准小反馈边数树宽分解，宽度是 $O(\sqrt q)$ 。这里 $q\le 34$ ，实际宽度可以控制在一个很小的常数范围内。即使保守按 $w\le 13$ 算，状态也只有 $2^{w+1}$ 级别。

DP 状态非常简单：

dp[\text{mask}][r]

含义：

当前 bag 中的点，哪些已经被某条已处理边选中过，用 mask 表示；
已经删掉了 $r$ 条边；
方案数为 $dp[\text{mask}][r]$ 。

注意：mask 只记录点是否已经被占用，不记录连通性。

3. 转移

设当前处理边为 $(u,v)$ 。

3.1 删除这条边

dp'[\text{mask}][r+1] += dp[\text{mask}][r].

3.2 保留边，并选择端点 $u$

如果 $u$ 还没被占用：

dp'[\text{mask}\cup \{u\}][r] += dp[\text{mask}][r].

3.3 保留边，并选择端点 $v$

如果 $v$ 还没被占用：

dp'[\text{mask}\cup \{v\}][r] += dp[\text{mask}][r].

这三种情况正好对应：

\text{删边},\quad p_i=a_i,\quad p_i=b_i.

4. nice tree decomposition 版本

如果用 nice TD，转移如下。

introduce vertex

新点加入 bag，初始一定未占用：

dp'[\text{mask}][r] += dp[\text{mask without new vertex}][r].

forget vertex

忘掉一个点时，不需要检查它是否被占用。

因为一个值可以不用出现在当前选出的坏位置里，这对应排列里该值没有被这些不合法位置占用。

所以：

dp'[\text{mask without }v][r] += dp[\text{mask}][r].

introduce edge

用上面“三选一”转移。

join

两个子树的边集互不相交，但 bag 顶点是共享的。
同一个顶点不能在左右两边都被占用，所以要求：

mask_1\ \&\ mask_2 = 0.

然后：

mask = mask_1 \mid mask_2.

转移为：

dp[mask][r_1+r_2] += dp_L[mask_1][r_1]\cdot dp_R[mask_2][r_2].

5. 为什么这严格等价于你的权值公式

对任意保留下来的边集 $S$ ，DP 数的是：每条边选择一个端点，且每个点最多被选一次。

考虑 $S$ 的一个连通分量 $K$ 。

若 $K$ 是树

|E_K|=|V_K|-1.

每条边都要选择一个端点，且每个点最多被选一次，所以最终恰好有一个点没被选。

树上只要指定那个没被选的点，其他边的选择方式唯一。

所以方案数是：

|V_K|.

这就是你写的树权值 $W(K)=|V(K)|$ 。

若 $K$ 是基环树

|E_K|=|V_K|.

所有点都必须被选一次。环上只有两个方向，环外树枝方向被唯一确定。

所以方案数是：

2.

这就是你写的基环树权值 $W(K)=2$ 。

若 $K$ 有两个及以上环

|E_K|>|V_K|.

边比点多，但每个点最多只能被选一次，不可能给每条边分配互不冲突的端点。

所以贡献为 $0$ 。

因此这个 DP 不需要判断“是不是 pseudoforest”，容量限制会自动过滤掉非法情况。

6. 复杂块为什么能过

复杂块的难点原本在于非树边数 $x$ 可能达到 $34$ ，直接 $2^x$ 枚举太大。

但换成 tree decomposition 后，状态只和 bag 里的点是否被占用有关：

O(2^w\cdot 34)

而不是

O(2^x).

复杂块的反馈边数

q=|E|-|V|+1\le 34.

小反馈边数图有小树宽，可以先把复杂块做 kernel：

去掉挂树；
压缩度为 $2$ 的长链；
剩下的核心点数、边数都是 $O(q)$ 。

压缩后的核心满足：

|V_{\text{core}}|\le 2q-2,\qquad |E_{\text{core}}|\le 3q-3.

也就是最多六七十个核心点。
在这个核心上求 tree decomposition，再把长链、挂树作为 transfer gadget 挂回去即可。

整体复杂度可以写成：

O\bigl(n\cdot 33^2 + \sum_{\text{complex }H} |TD_H|\cdot 2^{w_H}\cdot 33^2\bigr),

其中 $w_H$ 是复杂块核心的树宽，实际是很小的常数。

7. 最终算法框架

cpp
build multigraph G on values 1..n
for each i:
    add edge (a[i], b[i])

find connected components of G

cnt_tree = number of components with |E| = |V|-1
sum_pos = sum over components max(0, |E|-|V|)

if sum_pos > 33:
    answer = 0

for each component H:
    compute F_H[0..33]

    if H is tree:
        use ordinary tree DP
    else if H is unicyclic:
        use cycle + tree DP
    else:
        use tree-decomposition capacity DP:
            state = occupied mask of bag vertices
            transition per edge = delete / choose u / choose v

multiply all F_H into global C[0..33]

ans = 0
for m in 0..33:
    ans += (-1)^(n-m) * C[m] * fact[m]

print ans mod 2^32

核心结论就是：

复杂连通块不要 DP 连通性，也不要 DP 环结构。
直接在小树宽分解上 DP“点是否已经被某条保留边占用”。
树权值 $|V|$ 和基环树权值 $2$ 会自动从这个局部匹配计数里长出来。

Answer 2

可以确认，但要先纠正一点：

不能确认 $w_H=O(\sqrt{\mu_H})$ 这种上界。
这里 $\mu_H=|E_H|-|V_H|+1$ 是复杂连通块的环秩。仅由环秩控制 treewidth，最稳妥的通用上界是线性的：

w_H \le \mu_H+1.

在你的问题里，复杂连通块满足

D_H=|E_H|-|V_H|>0,

且

\sum_{D_C>0}D_C=t\le 33.

所以对任意复杂连通块：

D_H\le 33, \qquad \mu_H=D_H+1\le 34.

因此有严格上界：

w_H \le \mu_H+1 \le 35.

注意这里 $w_H$ 是 treewidth，bag 大小最多是 $w_H+1\le 36$ 。

1. $w_H\le \mu_H+1$ 的证明

取复杂连通块 $H$ 的一棵生成树 $T$ 。

非树边数量为

|E_H|-|V_H|+1=\mu_H.

设非树边集合为 $X$ ，对每条非树边任取一个端点放入集合 $S$ 。于是：

|S|\le |X|=\mu_H.

删除 $S$ 后，所有非树边都被破坏，剩下的图是生成树 $T$ 的子图，因此是森林。

也就是说：

H-S \text{ 是森林}.

森林的 treewidth 为 $1$ 。
对 $H-S$ 的树分解中每个 bag 加上整个 $S$ ，即可得到 $H$ 的树分解。

原森林 bag 大小最多为 $2$ ，加上 $|S|$ 后，bag 大小最多为：

|S|+2\le \mu_H+2.

所以 treewidth 至多：

\mu_H+1.

因此：

w_H\le \mu_H+1\le 35.

这个上界是严格的，但它只说明该 DP 是 FPT，不说明 $2^{35}$ 级别一定能过。后续若要“严格可过”，最好还要结合实际构造更小的 feedback vertex set / tree decomposition，或者改用专门的环秩 DP。

2. 复杂连通块 DP 的完整模型

对复杂连通块 $H=(V_H,E_H)$ ，我们要求它的局部生成函数：

F_H(y)=\sum_{r=0}^{33} f_H[r]y^r.

其中 $f_H[r]$ 表示：

在 $H$ 中删掉 $r$ 条边，剩余边每条选择一个端点，且每个点最多被选择一次的方案数。

这正是原二分图中局部匹配的计数。

3. DP 状态

取 $H$ 的一个 nice tree decomposition。

对 tree decomposition 的节点 $x$ ，设 bag 为 $B_x$ 。

令：

dp_x[S][r]

表示：

已经处理完 $x$ 子树内的所有 introduce edge；
当前 bag $B_x$ 中，被已经处理过的边占用的点集合为 $S\subseteq B_x$ ；
已经删掉了 $r$ 条边；
对应方案数为 $dp_x[S][r]$ 。

其中：

0\le r\le 33.

点是否被占用的含义是：

某条已经保留的边选择了这个点作为端点。

每个点最多被选择一次，因此同一个点不能被左右子树同时占用，也不能被多条边重复占用。

4. Leaf 节点

空 bag：

dp_{\text{leaf}}[\varnothing][0]=1.

其余状态为 $0$ 。

5. Introduce vertex 转移

引入一个新点 $v$ 。

子节点 bag 为 $B$ ，当前 bag 为：

B'=B\cup\{v\}.

因为 $v$ 刚出现，还没有任何已处理边可以占用它，所以：

dp_x[S][r] = dp_{\text{child}}[S][r],

其中要求：

v\notin S.

若 $v\in S$ ，则：

dp_x[S][r]=0.

6. Forget vertex 转移

忘掉一个点 $v$ 。

子节点 bag 为：

B'=B\cup\{v\},

当前 bag 为：

B.

忘掉点时不需要检查它是否已经被占用。因为原问题允许某个值没有被任何不合法位置使用。

所以：

dp_x[S][r] = dp_{\text{child}}[S][r] + dp_{\text{child}}[S\cup\{v\}][r].

也就是直接把 $v$ 是否被占用的两类状态合并。

7. Introduce edge 转移

引入一条边：

e=(u,v).

要求 $u,v\in B_x$ 。

这条边有三种选择：

7.1 删除这条边

dp_x[S][r+1] += dp_{\text{child}}[S][r].

7.2 保留这条边，并选择端点 $u$

如果：

u\notin S,

则：

dp_x[S\cup\{u\}][r] += dp_{\text{child}}[S][r].

7.3 保留这条边，并选择端点 $v$

如果：

v\notin S,

则：

dp_x[S\cup\{v\}][r] += dp_{\text{child}}[S][r].

这三种情况分别对应：

\text{删边},\quad \text{选 }u,\quad \text{选 }v.

如果存在重边，重边按不同边分别 introduce，重复做这套转移即可。

8. Join 转移

设当前节点 $x$ 有两个子节点 $l,r$ ，三者 bag 相同：

B_x=B_l=B_r.

左右子树处理的边集不相交，但 bag 里的点是共享的。

因此同一个 bag 点不能在左右两边同时被占用。

令左状态为 $S_1$ ，右状态为 $S_2$ ，必须满足：

S_1\cap S_2=\varnothing.

合并后：

S=S_1\cup S_2.

转移为：

dp_x[S][a+b] += dp_l[S_1][a]\cdot dp_r[S_2][b].

其中：

a+b\le 33.

9. Root 答案

根节点取空 bag。

则：

f_H[r]=dp_{\text{root}}[\varnothing][r].

于是复杂连通块的局部生成函数为：

F_H(y)=\sum_{r=0}^{33}dp_{\text{root}}[\varnothing][r]y^r.

10. 正确性说明

这个 DP 数的是：

每条边要么删除，要么选择一个端点，并且每个点最多被选择一次。

这正是原二分图中局部匹配的定义。

对任意保留边集 $S$ ，若它的某个连通分量是树，则：

|E|=|V|-1.

每条边选择一个互不冲突的端点，等价于恰好有一个点没被选。树上指定这个未被选的点后，所有边的方向唯一，因此贡献为：

|V|.

若某个连通分量是基环树，则：

|E|=|V|.

所有点都必须被选一次，环有两个方向，挂树方向被唯一确定，因此贡献为：

2.

若某个连通分量含有两个及以上环，则：

|E|>|V|.

边数多于点数，不可能给每条边分配互不冲突的端点，因此贡献自动为 $0$ 。

所以这个 DP 自动等价于你前面写的：

c_k= \sum_{\substack{F\subseteq G\\ |E(F)|=k\\ F\text{ is pseudoforest}}} \prod_{C\in F}W(C).

不需要显式维护连通性，也不需要显式判断树、环、基环树。

11. 复杂度

设 tree decomposition 的最大 bag 大小为 $B=w_H+1$ 。

状态数为：

2^B\cdot 34.

Introduce edge、introduce vertex、forget vertex 都是：

O(2^B\cdot 34).

Join 朴素转移为：

O(3^B\cdot 34^2),

因为每个 bag 点有三种归属：

\text{不被占用},\quad \text{左边占用},\quad \text{右边占用}.

因此总复杂度为：

O\left( |\mathrm{TD}|\cdot \left( 2^B\cdot 34 + 3^B\cdot 34^2 \right) \right).

用上界 $w_H\le 35$ ，也就是 $B\le 36$ ，这个复杂度在最坏情况下仍然太大。

所以结论是：

这个 DP 模型是正确且完整的，但仅靠 $w_H\le 35$ 不能证明严格可过。

下一步如果要实现并保证通过，需要继续做一层优化：不要使用通用 treewidth DP，而是利用 $\mu_H\le 34$ 的“环秩小”结构，构造更强的复杂块 DP。

Answer 3

可以，进一步优化后，我建议完全放弃通用 tree decomposition，改成：

在复杂连通块对应的“边-点关联二分图”上，做按环秩 $\mu$ 的匹配多项式递归。
递归复杂度可以严格压到
$O(\varphi^\mu \cdot \operatorname{poly}(33)+n\operatorname{poly}(33)),$
其中 $\varphi=\frac{1+\sqrt5}{2}$ ，且复杂块有
$\mu=|E|-|V|+1=D+1\le 34.$
所以最坏递归规模约为
$\varphi^{34}\approx 1.28\times 10^7,$
这是理论上足够小的。

这个方向比 $2^{34}$ 小很多，也比 treewidth DP 稳。

1. 关键转换：复杂块改成匹配多项式

对原图 $G$ 的一个复杂连通块 $H=(V_H,E_H)$ ，构造它的关联二分图 $B_H$ ：

左部点：原图 $H$ 的每条边 $e\in E_H$ ；
右部点：原图 $H$ 的每个点 $v\in V_H$ ；
若原图边 $e=(u,v)$ ，则在 $B_H$ 中连： $e-u,\quad e-v.$

那么在 $H$ 中保留一条边并选择一个端点，等价于在 $B_H$ 中匹配左点 $e$ 到右点 $u$ 或 $v$ 。

所以复杂块局部生成函数可以写成：

F_H(y)=\sum_{r=0}^{33} f_H[r]y^r,

其中 $f_H[r]$ 表示：

在 $B_H$ 中选一个匹配，使得恰好 $r$ 个左部点没有被匹配。

因为左部点就是原图边，所以：

r=\text{删掉的原图边数}.

于是：

f_H[r]=c_{\text{local},\,|E_H|-r}.

2. 关联二分图的环秩很小

如果 $H$ 连通，记：

D_H=|E_H|-|V_H|.

那么 $B_H$ 的点数是：

|V(B_H)|=|E_H|+|V_H|,

边数是：

|E(B_H)|=2|E_H|.

因此 $B_H$ 的环秩为：

\mu(B_H) = |E(B_H)|-|V(B_H)|+1 = 2|E_H|-(|E_H|+|V_H|)+1 = |E_H|-|V_H|+1 = D_H+1.

由于复杂块满足：

D_H\le 33,

所以：

\mu(B_H)\le 34.

后面所有复杂度都按这个 $\mu$ 控制，而不是按非树边 $2^x$ 枚举。

3. 子问题定义

对递归过程中得到的任意二分图 $B$ ，仍然区分左点和右点。

定义：

P_B(y)=\sum_{r=0}^{33} p_B[r]y^r,

其中 $p_B[r]$ 表示：

$B$ 的匹配中，恰好有 $r$ 个左点没有被匹配的方案数。

最后对复杂块 $H$ ：

F_H(y)=P_{B_H}(y).

所有多项式只保留 $0\sim 33$ 次项。

4. 基本化简

递归过程中始终做以下化简。

4.1 空图

P_{\varnothing}(y)=1.

4.2 孤立右点

孤立右点不影响左点是否匹配，直接删除：

P_B(y)=P_{B-r}(y).

4.3 孤立左点

孤立左点一定无法匹配，因此贡献一个 $y$ ：

P_B(y)=y\cdot P_{B-\ell}(y).

4.4 不连通图

若：

B=B_1\cup B_2\cup\cdots\cup B_s,

则：

P_B(y)=\prod_i P_{B_i}(y),

卷积时只保留 $0\sim 33$ 次项。

5. 森林与仙人掌作为多项式时间基底

如果当前二分图 $B$ 的环秩为 $0$ ，即它是森林，那么直接做树形匹配 DP，复杂度：

O(|B|\cdot 33^2).

如果当前图是仙人掌图，也建议作为基底直接 DP，而不是继续递归。

仙人掌图的每个双连通分量只有两类：

一条桥；
一个简单环。

可以在 block-cut tree 上 DP。每个割点保留两种状态：

0：该点未被当前子图匹配； \qquad 1：该点已被当前子图匹配。

桥块是普通边转移；环块可以断开成链，枚举割点端状态后做路径 DP。

仙人掌基底复杂度也是：

O(|B|\cdot 33^2).

这个基底很重要，因为如果全图只是很多环粘在一起，普通分支会退化到 $2^\mu$ ，而仙人掌 DP 可以线性处理。

6. 核心分支递归

如果当前图既不是森林，也不是仙人掌，那么它存在一个非简单环的双连通块。

在这个双连通块里，由于左点度数始终不超过 $2$ ，所以一定存在一个右点 $v$ ，其在该双连通块中的度数至少为 $3$ 。

取一条 incident edge：

e=(\ell,v),

其中：

$\ell$ 是左点；
$v$ 是右点；
$e$ 位于一个非仙人掌双连通块中；
$e$ 不是桥。

匹配递归为：

P_B(y) = P_{B-e}(y) + P_{B-\{\ell,v\}}(y).

含义：

情况 1：不使用匹配边 $e$

直接删掉这条二分图边：

P_{B-e}(y).

情况 2：使用匹配边 $e$

那么左点 $\ell$ 和右点 $v$ 都被匹配掉，删除这两个点：

P_{B-\{\ell,v\}}(y).

注意这里没有额外乘 $y$ ，因为左点 $\ell$ 已经被匹配了。

7. 为什么复杂度是 $\varphi^\mu$

令 $\mu(B)$ 为当前二分图的环秩：

\mu(B)=|E(B)|-|V(B)|+\#\operatorname{cc}(B).

7.1 删除边分支

因为 $e$ 在双连通块中，不是桥，所以删掉 $e$ 会让环秩下降 $1$ ：

\mu(B-e)=\mu(B)-1.

7.2 使用边分支

使用 $e=(\ell,v)$ 后，删除左点 $\ell$ 和右点 $v$ 。

在选取的双连通块中，右点 $v$ 的块内度数至少为 $3$ ，左点 $\ell$ 的块内度数为 $2$ 。

删除 $\ell,v$ 至少会让该双连通块的环秩下降 $2$ ，所以：

\mu(B-\{\ell,v\})\le \mu(B)-2.

因此递归规模满足：

T(\mu)\le T(\mu-1)+T(\mu-2)+\operatorname{poly}(33).

所以：

T(\mu)=O(\varphi^\mu).

由于复杂块：

\mu\le 34,

最坏递归节点数约为：

\varphi^{34}\approx 1.28\times 10^7.

这是可以接受的数量级。

8. DP 多项式转移细节

每个递归函数返回长度 $34$ 的数组：

P[0],P[1],\dots,P[33].

8.1 孤立左点

cpp
Q[r + 1] += P[r]

即整体左移一位。

8.2 不连通图合并

cpp
C[i + j] += A[i] * B[j]

只保留：

cpp
i + j <= 33

8.3 分支合并

cpp
P = P_without_edge + P_use_edge

逐项相加即可。

答案模 $2^{32}$ ，所以所有运算直接用 uint32_t 自然溢出即可。

9. 这个模型为什么等价于复杂块计数

原复杂块中，每条原图边 $e=(u,v)$ 有三种情况：

删除；
保留并选择端点 $u$ ；
保留并选择端点 $v$ 。

在关联二分图 $B_H$ 中：

左点 $e$ 没有被匹配：对应删除原图边 $e$ ；
左点 $e$ 匹配到右点 $u$ ：对应保留 $e$ ，并选择端点 $u$ ；
左点 $e$ 匹配到右点 $v$ ：对应保留 $e$ ，并选择端点 $v$ 。

匹配条件保证每个右点最多被选择一次。

所以 $B_H$ 中恰好 $r$ 个左点未匹配的匹配数，正是复杂块中删掉 $r$ 条边后的合法端点选择数。

因此：

F_H(y)=P_{B_H}(y)

严格成立。

10. 最终复杂块算法

对复杂连通块 $H$ ：

cpp
build incidence bipartite graph B_H

P = solve(B_H)

for r in 0..33:
    F_H[r] = P[r]

其中 solve(B)：

cpp
solve(B):
    remove isolated right vertices
    if isolated left vertex exists:
        return y * solve(B - isolated_left)

    split B into connected components
    if more than one component:
        return convolution of solve(component)

    if B is forest:
        return tree_matching_dp(B)

    if B is cactus:
        return cactus_matching_dp(B)

    find a non-cactus biconnected block
    find right vertex v with block-degree >= 3
    choose incident edge e = (left l, right v)

    A = solve(B - e)
    C = solve(B - {l, v})

    return A + C

11. 总复杂度

设复杂块 $H$ 的：

D_H=|E_H|-|V_H|, \qquad \mu_H=D_H+1.

则：

\operatorname{solve}(B_H) = O\left(\varphi^{\mu_H}\cdot 33^2 + |B_H|\cdot 33^2\right).

因为所有复杂块满足：

\sum_H D_H\le 33,

所以：

\mu_H\le 34.

最坏单块：

O(\varphi^{34}\cdot 33^2)

级别，理论上已经足够小。

12. 这个方案相对之前的优势

之前的非树边枚举是：

O(n\cdot 2^x),

其中 $x\le 34$ ，最坏：

2^{34}\approx 1.7\times 10^{10}.

现在递归是：

O(\varphi^{34}) \approx 1.28\times 10^7.

下降了约三位数量级。

而且这个递归直接算复杂块局部多项式，不需要维护：

连通性；
环方向；
树根；
pseudoforest 状态；
tree decomposition bag mask。

所有这些都被“关联二分图匹配”统一吸收掉了。

Answer 4

下面这份是优先可编译、可调试的完整 C++17 实现。

我按你的容斥框架做了：

\text{Ans}=\sum_{m=0}^{33}(-1)^{n-m}C[m]\cdot m!

其中 $C[m]=c_{n-m}$ 。

复杂连通块部分采用我前面说的“关联二分图匹配多项式”：

原图边变成左点；
原图点变成右点；
一条原图边 $(u,v)$ 对应左点连向右点 $u,v$ ；
左点未匹配等价于删掉这条原图边；
每个右点最多匹配一次等价于每个值最多被一个不合法位置占用。

代码里还做了：

孤立左点/右点化简；
连通块拆分；
cactus 图匹配 DP；
非 cactus 块用分支： $P_G=P_{G-e}+P_{G-\{u,v\}}$
uint32_t 自然溢出实现模 $2^{32}$ 。

我已经用小规模随机数据和暴力排列对拍过一轮， $n\le 8$ 随机样例通过。后面我们可以继续针对极端结构对拍和压性能。

cpp
#include <bits/stdc++.h>
using namespace std;

static const int LIM = 33;
using Poly = array<uint32_t, LIM + 1>;

static inline Poly zero_poly() {
    Poly p{};
    return p;
}

static inline Poly one_poly() {
    Poly p{};
    p[0] = 1;
    return p;
}

static inline bool is_zero_poly(const Poly &p) {
    for (uint32_t x : p) {
        if (x) return false;
    }
    return true;
}

static inline Poly add_poly(const Poly &a, const Poly &b) {
    Poly c{};
    for (int i = 0; i <= LIM; ++i) {
        c[i] = a[i] + b[i];
    }
    return c;
}

static inline void add_to(Poly &a, const Poly &b) {
    for (int i = 0; i <= LIM; ++i) {
        a[i] += b[i];
    }
}

static inline Poly mul_poly(const Poly &a, const Poly &b) {
    Poly c{};
    for (int i = 0; i <= LIM; ++i) {
        if (!a[i]) continue;
        for (int j = 0; i + j <= LIM; ++j) {
            if (!b[j]) continue;
            c[i + j] += (uint32_t)((uint64_t)a[i] * (uint64_t)b[j]);
        }
    }
    return c;
}

static inline Poly shift_poly(const Poly &a, int s) {
    Poly c{};
    if (s > LIM) return c;
    for (int i = 0; i + s <= LIM; ++i) {
        c[i + s] = a[i];
    }
    return c;
}

struct BGraph {
    int N = 0;
    vector<unsigned char> side; // 0 = left, 1 = right
    vector<pair<int, int>> edges;
    vector<unsigned char> aliveV, aliveE;
};

struct BCC {
    vector<int> edges;
    vector<int> verts;
};

static vector<vector<pair<int, int>>> build_adj(const BGraph &g) {
    vector<vector<pair<int, int>>> adj(g.N);
    for (int eid = 0; eid < (int)g.edges.size(); ++eid) {
        if (!g.aliveE[eid]) continue;
        auto [u, v] = g.edges[eid];
        if (!g.aliveV[u] || !g.aliveV[v]) continue;
        adj[u].push_back({v, eid});
        adj[v].push_back({u, eid});
    }
    return adj;
}

// 删除孤立右点；孤立左点必须未匹配，因此贡献一个 y。
static int simplify_graph(BGraph &g) {
    int shift = 0;
    bool changed = true;

    while (changed) {
        changed = false;
        vector<int> deg(g.N, 0);

        for (int eid = 0; eid < (int)g.edges.size(); ++eid) {
            if (!g.aliveE[eid]) continue;
            auto [u, v] = g.edges[eid];

            if (!g.aliveV[u] || !g.aliveV[v]) {
                g.aliveE[eid] = 0;
                changed = true;
                continue;
            }

            ++deg[u];
            ++deg[v];
        }

        for (int v = 0; v < g.N; ++v) {
            if (!g.aliveV[v]) continue;
            if (deg[v] == 0) {
                if (g.side[v] == 0) ++shift;
                g.aliveV[v] = 0;
                changed = true;
            }
        }
    }

    return shift;
}

static int active_edge_count(const BGraph &g) {
    int cnt = 0;
    for (int eid = 0; eid < (int)g.edges.size(); ++eid) {
        if (!g.aliveE[eid]) continue;
        auto [u, v] = g.edges[eid];
        if (g.aliveV[u] && g.aliveV[v]) ++cnt;
    }
    return cnt;
}

static BGraph induced_subgraph(
    const BGraph &g,
    const vector<int> &nodes,
    const vector<int> &edgeIds
) {
    BGraph h;
    h.N = (int)nodes.size();
    h.side.assign(h.N, 0);
    h.aliveV.assign(h.N, 1);

    vector<int> id(g.N, -1);

    for (int i = 0; i < (int)nodes.size(); ++i) {
        id[nodes[i]] = i;
        h.side[i] = g.side[nodes[i]];
    }

    for (int eid : edgeIds) {
        auto [u, v] = g.edges[eid];
        if (id[u] < 0 || id[v] < 0) continue;
        h.edges.push_back({id[u], id[v]});
    }

    h.aliveE.assign(h.edges.size(), 1);
    return h;
}

struct ComponentsResult {
    vector<vector<int>> compNodes;
    vector<vector<int>> compEdges;
};

static ComponentsResult get_components(
    const BGraph &g,
    const vector<vector<pair<int, int>>> &adj
) {
    ComponentsResult res;
    vector<unsigned char> vis(g.N, 0);
    vector<unsigned char> seenE(g.edges.size(), 0);

    for (int s = 0; s < g.N; ++s) {
        if (!g.aliveV[s] || vis[s]) continue;
        if (adj[s].empty()) continue;

        vector<int> nodes, eids;
        queue<int> q;
        vis[s] = 1;
        q.push(s);

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            nodes.push_back(u);

            for (auto [v, eid] : adj[u]) {
                if (!seenE[eid]) {
                    seenE[eid] = 1;
                    eids.push_back(eid);
                }

                if (!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }

        res.compNodes.push_back(move(nodes));
        res.compEdges.push_back(move(eids));
    }

    return res;
}

static vector<BCC> get_bccs(
    const BGraph &g,
    const vector<vector<pair<int, int>>> &adj
) {
    vector<int> disc(g.N, 0), low(g.N, 0), st;
    vector<BCC> bccs;
    int timer = 0;

    vector<int> mark(g.N, 0);
    int token = 1;

    function<void(int, int)> dfs = [&](int u, int pe) {
        disc[u] = low[u] = ++timer;

        for (auto [v, eid] : adj[u]) {
            if (eid == pe) continue;

            if (!disc[v]) {
                st.push_back(eid);
                dfs(v, eid);
                low[u] = min(low[u], low[v]);

                if (low[v] >= disc[u]) {
                    vector<int> es;

                    while (true) {
                        int x = st.back();
                        st.pop_back();
                        es.push_back(x);
                        if (x == eid) break;
                    }

                    vector<int> vs;
                    ++token;

                    if (token == INT_MAX) {
                        fill(mark.begin(), mark.end(), 0);
                        token = 1;
                    }

                    for (int x : es) {
                        auto [a, b] = g.edges[x];

                        if (mark[a] != token) {
                            mark[a] = token;
                            vs.push_back(a);
                        }

                        if (mark[b] != token) {
                            mark[b] = token;
                            vs.push_back(b);
                        }
                    }

                    bccs.push_back({move(es), move(vs)});
                }
            } else if (disc[v] < disc[u]) {
                st.push_back(eid);
                low[u] = min(low[u], disc[v]);
            }
        }
    };

    for (int i = 0; i < g.N; ++i) {
        if (g.aliveV[i] && !adj[i].empty() && !disc[i]) {
            dfs(i, -1);
        }
    }

    return bccs;
}

static bool block_is_cycle(const BGraph &g, const BCC &b) {
    if ((int)b.edges.size() == 1) return false;
    if (b.edges.size() != b.verts.size()) return false;

    unordered_map<int, int> deg;
    deg.reserve(b.verts.size() * 2 + 1);

    for (int v : b.verts) {
        deg[v] = 0;
    }

    for (int eid : b.edges) {
        auto [u, v] = g.edges[eid];
        ++deg[u];
        ++deg[v];
    }

    for (auto &kv : deg) {
        if (kv.second != 2) return false;
    }

    return true;
}

static bool is_cactus_graph(const BGraph &g, const vector<BCC> &bccs) {
    for (const auto &b : bccs) {
        if ((int)b.edges.size() == 1) continue;
        if (!block_is_cycle(g, b)) return false;
    }
    return true;
}

struct CactusSolver {
    const BGraph &g;
    const vector<BCC> &bccs;
    vector<vector<int>> vBlocks;
    unordered_map<long long, pair<Poly, Poly>> memoVertex;

    CactusSolver(const BGraph &g_, const vector<BCC> &bccs_)
        : g(g_), bccs(bccs_) {
        vBlocks.assign(g.N, {});

        for (int i = 0; i < (int)bccs.size(); ++i) {
            for (int v : bccs[i].verts) {
                vBlocks[v].push_back(i);
            }
        }
    }

    Poly monomer(int v) const {
        Poly p{};

        if (g.side[v] == 0) {
            p[1] = 1; // unmatched left vertex contributes y
        } else {
            p[0] = 1; // unmatched right vertex contributes 1
        }

        return p;
    }

    pair<Poly, Poly> solve_vertex(int v, int parentBlock) {
        long long key =
            (static_cast<long long>(v) << 32)
            ^ static_cast<unsigned int>(parentBlock + 1);

        auto it = memoVertex.find(key);
        if (it != memoVertex.end()) return it->second;

        // state 0: v is not matched by any child block
        // state 1: v is matched by exactly one child block
        Poly unusedByChildren = one_poly();
        Poly usedByChildren = zero_poly();

        for (int bid : vBlocks[v]) {
            if (bid == parentBlock) continue;

            auto bp = solve_block(bid, v);

            Poly n0 = mul_poly(unusedByChildren, bp.first);
            Poly n1 = add_poly(
                mul_poly(usedByChildren, bp.first),
                mul_poly(unusedByChildren, bp.second)
            );

            unusedByChildren = n0;
            usedByChildren = n1;
        }

        auto ans = make_pair(unusedByChildren, usedByChildren);
        memoVertex.emplace(key, ans);
        return ans;
    }

    Poly vertex_weight_inside_block(
        int v,
        int parentBlock,
        int matchedByThisBlock
    ) {
        auto base = solve_vertex(v, parentBlock);

        if (matchedByThisBlock) {
            // 子块不能已经匹配 v。
            return base.first;
        } else {
            // 要么子块匹配 v，要么 v 完全未匹配，此时支付 monomer。
            return add_poly(base.second, mul_poly(base.first, monomer(v)));
        }
    }

    vector<int> cycle_order(int bid, int parentVertex) {
        const BCC &b = bccs[bid];
        int L = (int)b.verts.size();

        unordered_map<int, int> loc;
        loc.reserve(L * 2 + 1);

        for (int i = 0; i < L; ++i) {
            loc[b.verts[i]] = i;
        }

        vector<vector<int>> ladj(L);

        for (int eid : b.edges) {
            auto [u, v] = g.edges[eid];
            int a = loc[u];
            int c = loc[v];
            ladj[a].push_back(c);
            ladj[c].push_back(a);
        }

        int s = loc[parentVertex];

        vector<int> ord;
        ord.reserve(L);
        ord.push_back(parentVertex);

        int prev = s;
        int cur = ladj[s][0];

        while (cur != s) {
            ord.push_back(b.verts[cur]);

            int nxt = (ladj[cur][0] == prev)
                ? ladj[cur][1]
                : ladj[cur][0];

            prev = cur;
            cur = nxt;
        }

        return ord;
    }

    pair<Poly, Poly> solve_block(int bid, int parentVertex) {
        const BCC &b = bccs[bid];

        if ((int)b.edges.size() == 1) {
            int eid = b.edges[0];
            auto [a, c] = g.edges[eid];
            int u = (a == parentVertex ? c : a);

            Poly noUseParent = vertex_weight_inside_block(u, bid, 0);
            Poly useParent = vertex_weight_inside_block(u, bid, 1);

            return {noUseParent, useParent};
        }

        vector<int> ord = cycle_order(bid, parentVertex);
        int L = (int)ord.size();

        vector<array<Poly, 2>> w(L);

        for (int i = 1; i < L; ++i) {
            w[i][0] = vertex_weight_inside_block(ord[i], bid, 0);
            w[i][1] = vertex_weight_inside_block(ord[i], bid, 1);
        }

        Poly res0 = zero_poly();
        Poly res1 = zero_poly();

        // first 表示边 (0,1) 是否选入匹配。
        // last 表示边 (L-1,0) 是否选入匹配。
        for (int first = 0; first <= 1; ++first) {
            for (int last = 0; last <= 1; ++last) {
                if (first && last) continue;

                int parentUsed = first | last;

                array<Poly, 2> dp{zero_poly(), zero_poly()};
                dp[first] = one_poly();

                for (int i = 1; i < L; ++i) {
                    array<Poly, 2> ndp{zero_poly(), zero_poly()};

                    for (int prev = 0; prev <= 1; ++prev) {
                        if (is_zero_poly(dp[prev])) continue;

                        if (i == L - 1) {
                            int nxt = last;
                            if (prev && nxt) continue;

                            int matched = prev | nxt;
                            add_to(
                                ndp[nxt],
                                mul_poly(dp[prev], w[i][matched])
                            );
                        } else {
                            for (int nxt = 0; nxt <= 1; ++nxt) {
                                if (prev && nxt) continue;

                                int matched = prev | nxt;
                                add_to(
                                    ndp[nxt],
                                    mul_poly(dp[prev], w[i][matched])
                                );
                            }
                        }
                    }

                    dp = ndp;
                }

                if (parentUsed) {
                    add_to(res1, dp[last]);
                } else {
                    add_to(res0, dp[last]);
                }
            }
        }

        return {res0, res1};
    }

    Poly solve() {
        int root = -1;

        for (int i = 0; i < g.N; ++i) {
            if (g.aliveV[i] && !vBlocks[i].empty()) {
                root = i;
                break;
            }
        }

        if (root == -1) return one_poly();

        auto base = solve_vertex(root, -1);

        // 根点没有父块，所以最后如果根未匹配，要支付 monomer。
        return add_poly(base.second, mul_poly(base.first, monomer(root)));
    }
};

static int find_branch_edge(const BGraph &g, const vector<BCC> &bccs) {
    vector<int> deg(g.N, 0), touched;

    for (const BCC &b : bccs) {
        bool bad = false;

        if ((int)b.edges.size() != 1 && !block_is_cycle(g, b)) {
            bad = true;
        }

        if (!bad) continue;

        touched.clear();

        for (int v : b.verts) {
            deg[v] = 0;
            touched.push_back(v);
        }

        for (int eid : b.edges) {
            auto [u, v] = g.edges[eid];
            ++deg[u];
            ++deg[v];
        }

        int rv = -1;

        for (int v : b.verts) {
            if (g.side[v] == 1 && deg[v] >= 3) {
                rv = v;
                break;
            }
        }

        if (rv != -1) {
            for (int eid : b.edges) {
                auto [u, v] = g.edges[eid];
                if (u == rv || v == rv) return eid;
            }
        }

        // 理论上不会走到这里；保底选这个非 cactus 块的一条边。
        return b.edges[0];
    }

    return -1;
}

static Poly solve_bgraph(BGraph g);

static Poly solve_connected_bgraph(
    BGraph &g,
    const vector<vector<pair<int, int>>> &adj
) {
    vector<BCC> bccs = get_bccs(g, adj);

    if (is_cactus_graph(g, bccs)) {
        CactusSolver solver(g, bccs);
        return solver.solve();
    }

    int eid = find_branch_edge(g, bccs);

    if (eid < 0) {
        return zero_poly();
    }

    // 不选这条匹配边。
    BGraph g0 = g;
    g0.aliveE[eid] = 0;
    Poly A = solve_bgraph(g0);

    // 选这条匹配边：删除两个端点。
    BGraph g1 = g;
    auto [u, v] = g1.edges[eid];

    if (g1.aliveV[u]) g1.aliveV[u] = 0;
    if (g1.aliveV[v]) g1.aliveV[v] = 0;

    for (int i = 0; i < (int)g1.edges.size(); ++i) {
        if (!g1.aliveE[i]) continue;

        auto [a, b] = g1.edges[i];

        if (a == u || a == v || b == u || b == v) {
            g1.aliveE[i] = 0;
        }
    }

    Poly B = solve_bgraph(g1);

    return add_poly(A, B);
}

static Poly solve_bgraph(BGraph g) {
    int shift = simplify_graph(g);

    if (shift > LIM) {
        return zero_poly();
    }

    if (active_edge_count(g) == 0) {
        return shift_poly(one_poly(), shift);
    }

    auto adj = build_adj(g);
    auto comps = get_components(g, adj);

    if ((int)comps.compNodes.size() >= 2) {
        Poly prod = one_poly();

        for (int i = 0; i < (int)comps.compNodes.size(); ++i) {
            BGraph sub = induced_subgraph(
                g,
                comps.compNodes[i],
                comps.compEdges[i]
            );

            prod = mul_poly(prod, solve_bgraph(sub));
        }

        return shift_poly(prod, shift);
    }

    Poly core = solve_connected_bgraph(g, adj);
    return shift_poly(core, shift);
}

static BGraph build_incidence_component(
    const vector<int> &compVerts,
    const vector<int> &compEdges,
    const vector<int> &oa,
    const vector<int> &ob,
    vector<int> &tmpMap
) {
    int m = (int)compEdges.size();
    int vcnt = (int)compVerts.size();

    BGraph g;
    g.N = m + vcnt;
    g.side.assign(g.N, 1);

    for (int i = 0; i < m; ++i) {
        g.side[i] = 0;
    }

    for (int i = 0; i < vcnt; ++i) {
        tmpMap[compVerts[i]] = m + i;
    }

    for (int i = 0; i < m; ++i) {
        int eid = compEdges[i];
        int u = oa[eid];
        int v = ob[eid];

        g.edges.push_back({i, tmpMap[u]});
        g.edges.push_back({i, tmpMap[v]});
    }

    for (int x : compVerts) {
        tmpMap[x] = -1;
    }

    g.aliveV.assign(g.N, 1);
    g.aliveE.assign(g.edges.size(), 1);

    return g;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;

    if (!(cin >> n)) return 0;

    vector<int> a(n), b(n);

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }

    vector<vector<int>> origAdj(n + 1);

    for (int i = 0; i < n; ++i) {
        origAdj[a[i]].push_back(i);
        origAdj[b[i]].push_back(i);
    }

    vector<unsigned char> visV(n + 1, 0), visE(n, 0);
    vector<vector<int>> allCompVerts, allCompEdges;

    int treeComponents = 0;

    for (int s = 1; s <= n; ++s) {
        if (visV[s]) continue;

        vector<int> verts, edges;
        queue<int> q;

        visV[s] = 1;
        q.push(s);

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            verts.push_back(u);

            for (int eid : origAdj[u]) {
                if (!visE[eid]) {
                    visE[eid] = 1;
                    edges.push_back(eid);
                }

                int v = a[eid] ^ b[eid] ^ u;

                if (!visV[v]) {
                    visV[v] = 1;
                    q.push(v);
                }
            }
        }

        if ((int)edges.size() == (int)verts.size() - 1) {
            ++treeComponents;
        }

        allCompVerts.push_back(move(verts));
        allCompEdges.push_back(move(edges));
    }

    if (treeComponents > LIM) {
        cout << 0 << '\n';
        return 0;
    }

    Poly global = one_poly();
    vector<int> tmpMap(n + 1, -1);

    for (int cid = 0; cid < (int)allCompVerts.size(); ++cid) {
        const auto &verts = allCompVerts[cid];
        const auto &edges = allCompEdges[cid];

        Poly local = one_poly();

        if (!edges.empty()) {
            BGraph bg = build_incidence_component(
                verts,
                edges,
                a,
                b,
                tmpMap
            );

            local = solve_bgraph(bg);
        }

        global = mul_poly(global, local);
    }

    uint32_t fact[LIM + 1];

    fact[0] = 1;

    for (int i = 1; i <= LIM; ++i) {
        fact[i] = fact[i - 1] * (uint32_t)i;
    }

    uint32_t ans = 0;

    for (int m = 0; m <= LIM; ++m) {
        uint32_t term =
            (uint32_t)((uint64_t)global[m] * (uint64_t)fact[m]);

        int k = n - m;

        if (k & 1) {
            ans -= term;
        } else {
            ans += term;
        }
    }

    cout << (uint32_t)ans << '\n';
    return 0;
}

编译：

bash
g++ -std=c++17 -O2 -pipe -static -s main.cpp -o main

读入格式我先按你题面描述写成：

text
n
a1 a2 ... an
b1 b2 ... bn

如果原题输入是每行一组 a_i b_i，只需要改 main() 里的读入部分。

Answer 5

有。最推荐的卡法是：

构造一个 $D=33$ 的单个复杂连通块，再加 33 个孤立点。
这样全图仍然满足 $|E|=|V|=n$ ，并且复杂块的关联二分图环秩达到最大：
$\mu=D+1=34.$
这是你当前算法需要处理的最大理论边界。

不要用“两个点之间挂很多重边”那种图，它看起来 $D=33$ ，但分支后很快退化成星，实际不难。

更好的卡法是用一个 66 点 99 边的 3-正则双连通图 作为复杂核心：

|V|=66,\quad |E|=99,\quad D=33.

然后如果想卡大 $n$ ，就在这个核心的边上做细分。细分一条边会同时增加一个点和一条边，不改变 $D$ ，所以复杂度边界仍然卡满。

下面给你一个 Python gen。

用法：

bash
python3 gen_hard.py 99 1 > hard_99.in
python3 gen_hard.py 200000 1 > hard_200000.in

其中：

99：纯递归压力，复杂核心最小但 $D=33$ ；
200000：递归压力 + 大图扫描/拷贝压力；
第二个参数是随机种子。

python
#!/usr/bin/env python3
import sys
import random
from collections import deque

CORE_V = 66
CORE_DEG = 3
CORE_E = CORE_V * CORE_DEG // 2
EXCESS = 33


def connected(n, edges):
    g = [[] for _ in range(n)]
    for u, v in edges:
        g[u].append(v)
        g[v].append(u)

    vis = [False] * n
    q = deque([0])
    vis[0] = True

    while q:
        u = q.popleft()
        for v in g[u]:
            if not vis[v]:
                vis[v] = True
                q.append(v)

    return all(vis)


def biconnected(n, edges):
    g = [[] for _ in range(n)]
    for eid, (u, v) in enumerate(edges):
        g[u].append((v, eid))
        g[v].append((u, eid))

    disc = [0] * n
    low = [0] * n
    timer = 0
    ok = True

    def dfs(u, pe):
        nonlocal timer, ok
        timer += 1
        disc[u] = low[u] = timer
        child = 0

        for v, eid in g[u]:
            if eid == pe:
                continue

            if disc[v] == 0:
                child += 1
                dfs(v, eid)
                low[u] = min(low[u], low[v])

                if pe != -1 and low[v] >= disc[u]:
                    ok = False
            else:
                low[u] = min(low[u], disc[v])

        if pe == -1 and child >= 2:
            ok = False

    dfs(0, -1)

    if not all(disc):
        return False

    return ok


def random_cubic_biconnected(seed):
    random.seed(seed)

    for attempt in range(200000):
        stubs = []
        for i in range(CORE_V):
            for _ in range(CORE_DEG):
                stubs.append(i)

        random.shuffle(stubs)

        edges = []
        used = set()
        bad = False

        for i in range(0, len(stubs), 2):
            u = stubs[i]
            v = stubs[i + 1]

            if u == v:
                bad = True
                break

            if u > v:
                u, v = v, u

            if (u, v) in used:
                bad = True
                break

            used.add((u, v))
            edges.append((u, v))

        if bad:
            continue

        if len(edges) != CORE_E:
            continue

        if not connected(CORE_V, edges):
            continue

        if not biconnected(CORE_V, edges):
            continue

        return edges

    raise RuntimeError("failed to generate random cubic biconnected graph")


def deterministic_core():
    # 66 点 3-正则图：C_66 + 对径匹配。
    # 这个比较稳定，但没有随机 3-正则图那么狠。
    edges = []

    for i in range(CORE_V):
        u = i
        v = (i + 1) % CORE_V
        if u > v:
            u, v = v, u
        edges.append((u, v))

    for i in range(CORE_V // 2):
        edges.append((i, i + CORE_V // 2))

    edges = sorted(set(edges))
    assert len(edges) == CORE_E
    assert connected(CORE_V, edges)
    assert biconnected(CORE_V, edges)

    return edges


def build_instance(n, seed):
    if n < 99:
        raise ValueError("hard max-D instance needs n >= 99")

    # 用随机 3-正则双连通核心。
    # 如果想要完全确定性的核心，可以改成 deterministic_core()。
    core_edges = random_cubic_biconnected(seed)
    # core_edges = deterministic_core()

    extra = n - 99

    # 把 extra 个细分点尽量均匀撒到核心边上。
    sub = [0] * len(core_edges)
    order = list(range(len(core_edges)))
    random.shuffle(order)

    for i in range(extra):
        sub[order[i % len(order)]] += 1

    cur_v = CORE_V
    out_edges = []

    for idx, (u, v) in enumerate(core_edges):
        last = u

        for _ in range(sub[idx]):
            cur_v += 1
            out_edges.append((last, cur_v - 1))
            last = cur_v - 1

        out_edges.append((last, v))

    # 复杂块点数应该是 n - 33，边数应该是 n。
    complex_v = cur_v
    assert complex_v == n - EXCESS
    assert len(out_edges) == n

    # 把点编号改成 1-based。
    out_edges = [(u + 1, v + 1) for u, v in out_edges]

    # 剩下 33 个点是孤立点，编号为 complex_v+1 ... n。
    # 它们不会出现在任何边中。

    # 打乱边顺序和端点方向，避免算法吃到特殊顺序福利。
    random.shuffle(out_edges)

    a = []
    b = []

    for u, v in out_edges:
        if random.randint(0, 1):
            u, v = v, u
        a.append(u)
        b.append(v)

    return a, b


def main():
    if len(sys.argv) < 2:
        print("usage: python3 gen_hard.py n [seed]", file=sys.stderr)
        sys.exit(1)

    n = int(sys.argv[1])
    seed = int(sys.argv[2]) if len(sys.argv) >= 3 else 1

    a, b = build_instance(n, seed)

    print(n)
    print(*a)
    print(*b)


if __name__ == "__main__":
    main()

为什么这个 gen 能卡边界

复杂核心满足：

|V_{\text{core}}|=66,\quad |E_{\text{core}}|=99.

所以：

D=|E|-|V|=33.

再加上 33 个孤立点后：

|V|=66+33=99,\quad |E|=99.

如果把边细分到 $n=200000$ ，每细分一次：

|V|\leftarrow |V|+1,\quad |E|\leftarrow |E|+1,

所以 $D$ 不变，仍然是：

D=33.

因此复杂块的关联二分图环秩始终是：

\mu=D+1=34.

这是当前只算 $m\le 33$ 方案下能遇到的最大复杂块。

建议你这样卡

先测纯递归压力：

bash
python3 gen_hard.py 99 1 > hard_99_1.in
python3 gen_hard.py 99 2 > hard_99_2.in
python3 gen_hard.py 99 3 > hard_99_3.in

再测大图压力：

bash
python3 gen_hard.py 200000 1 > hard_200000_1.in
python3 gen_hard.py 200000 2 > hard_200000_2.in
python3 gen_hard.py 200000 3 > hard_200000_3.in

如果你当前这份实现被 hard_200000 卡死，那基本可以确认瓶颈不是数学 DP，而是复杂块没有先压缩核心：递归中反复复制、Tarjan、扫整张细分后的大图。

下一步要优化的话，方向很明确：

先把复杂连通块压成 $O(D)$ 规模核心，把长链变成 transfer gadget。
对 $D=33$ ，核心规模只有常数级，递归才真正理论可过。

Answer 6

对，前一个方案本质上还是不够稳。炸的原因不是代码细节，而是分支对象选错了：

之前是在“原始关联二分图”上递归，每个分支都反复 Tarjan、复制、扫大图；而且删一条关联边后产生的大量度 $1$ 链没有被一次性吸收，导致随机极限核心也会炸。

需要把模型再换一次：
把复杂块转成带点权的 monomer-dimer 问题，然后每次递归前强制压到 2-core。

这样才能把复杂度真正压到由 excess 控制，而不是由 $n$ 或随机核心的边数控制。

1. 先加一个关键剪枝

设原图 $G$ 的连通块 excess 为：

D_C=|E_C|-|V_C|.

令：

P=\sum_C \max(0,D_C).

那么至少要删 $P$ 条边才可能让所有正 excess 块变成 pseudoforest。

所以：

cpp
if (P > 33) ans = 0;

更重要的是：

cpp
if (P == 33) ans = 0;

原因是：此时只可能有 $m=33$ 项。每个正 excess 块都必须做“最少删除”，保留下来的每个有效块至少含有一个基环树分量，权值至少含一个因子 $2$ 。因此 $C[33]$ 必然是偶数，而

v_2(33!)=31.

所以：

C[33]\cdot 33! \equiv 0 \pmod {2^{32}}.

这会直接干掉你构造的 $D=33$ 极限核心。

2. 新模型：monomer-dimer 点权模型

对每个原图连通块 $H$ ，仍然构造关联二分图 $B_H$ 。

原图边 $e$ 变成左点；
原图点 $v$ 变成右点；
若 $e=(u,v)$ ，则左点 $e$ 连向右点 $u,v$ 。

现在把它看成 monomer-dimer 模型。

每个点 $x$ 有两个权值：

F_x=\text{点 }x\text{ 没有被匹配时的权值},

B_x=\text{点 }x\text{ 被匹配时的权值}.

初始时：

左点，也就是原图边：
$F_x=y,\qquad B_x=1.$
左点未匹配等价于删掉这条原图边。
右点，也就是原图值域点：
$F_x=1,\qquad B_x=1.$

于是目标多项式就是：

Z(B_H)= \sum_{M} \prod_{x\notin V(M)}F_x \prod_{x\in V(M)}B_x.

这正好等价于：

\sum_r f_H[r]y^r.

3. 最关键的优化：每次递归前压 2-core

这是前一个代码缺失的核心。

在当前递归图中，不允许直接分支。
必须先把所有度 $0$ 、度 $1$ 点剥掉，并把它们变成核心点的点权。

对于一棵被剥掉的树，设它向父亲传递两个多项式：

$A_u$ ： $u$ 不被父边匹配；
$C_u$ ： $u$ 被父边匹配。

若 $u$ 的剥离子节点为 $ch(u)$ ，则：

C_u = B_u \prod_{v\in ch(u)} A_v.

A_u = F_u \prod_{v\in ch(u)} A_v + B_u \sum_{v\in ch(u)} C_v \prod_{w\in ch(u),w\ne v}A_w.

含义：

如果 $u$ 被父边匹配，则 $u$ 不能再匹配任何儿子；
如果 $u$ 不被父边匹配，则它要么自己未匹配，要么匹配恰好一个儿子。

如果剥离树挂在核心点 $r$ 上，那么它作为 $r$ 的一个儿子被合并进 $r$ 的点权。

设核心点 $r$ 原本权值为 $F_r,B_r$ ，挂上的子树消息为 $(A_i,C_i)$ ，则更新后：

B'_r = B_r \prod_i A_i.

F'_r = F_r \prod_i A_i + B_r \sum_i C_i \prod_{j\ne i}A_j.

如果整个连通块被剥空了，则它就是树，直接返回根的 $A$ 。

4. 为什么这一步能救复杂度

以你卡的随机 3-正则核心为例。

原始关联二分图中：

左点度数 $2$ ；
右点度数 $3$ 。

如果你删掉一条关联边，那个左点立刻变成度 $1$ 。

旧做法会继续在大图上递归。

新做法会立刻把这个度 $1$ 左点以及后续产生的整条链全部吸收成点权。

也就是说，分支后不会留下大量“半死不活”的路径结构。

这会把递归规模从“随机核心指数爆炸”压成真正按 excess 下降。

5. 递归只在 2-core 上进行

压完 2-core 后有几种情况。

情况一：核心为空

返回剥离树的结果。

情况二：不连通

分别求解后卷积。

情况三：核心是 cactus

直接做 block-cut tree DP。

这里需要用带点权版本：

点未被块内边匹配时，用 $F_x$ ；
点被块内边匹配时，用 $B_x$ 。

桥块、环块都可以线性 DP。

情况四：存在非 cactus 双连通块

在这个块里选一条边 $e=(u,v)$ ，做 monomer-dimer 标准分支：

Z(G)=Z(G-e)+B_uB_v Z(G-u-v).

注意第二项要乘：

B_uB_v.

旧代码里用的是普通匹配模型，点被匹配的权值默认是 $1$ ，所以没体现这一层。
新模型必须带上这个因子。

6. 递归伪代码

cpp
solve(G):
    reduce_to_2core(G)

    if G is empty:
        return accumulated_factor

    split connected components
    if multiple:
        return product solve(component)

    if G is cactus:
        return cactus_dp(G)

    choose edge (u, v) inside a non-cactus biconnected block

    A = solve(G - edge(u, v))

    B = solve(G - vertices u, v)
    B *= block[u] * block[v]

    return A + B

所有多项式只保留到 $33$ 次。

7. 递归选边策略

不要随便选边。

优先选：

位于非 cactus 双连通块中；
至少一个端点当前度数 $\ge 3$ ；
两端度数和最大的边。

也就是：

cpp
best_edge = argmax(deg[u] + deg[v])

这样使用分支 $G-u-v$ 时，能最大化一次性剥掉的结构。

8. 再加一个“按答案精度”的优化

最终项是：

C[m]\cdot m!.

所以 $C[m]$ 只需要模：

2^{32-v_2(m!)}.

例如：

$m$	$v_2(m!)$	$C[m]$ 需要的位数
24	22	10
28	25	7
30	26	6
31	26	6
32	31	1
33	31	1

所以不要全程都用 uint32_t 算满 $2^{32}$ 。

每个系数 $m$ 可以按需要截断：

cpp
need[m] = max(0, 32 - v2_fact[m]);
mod[m] = 1u << need[m]; // need=32 时特殊处理

更简单的工程做法是：

多项式仍然用 uint32_t；
每次加法、乘法后，对第 $i$ 项按 mask[i] 截断；
对 $i=32,33$ 只保留奇偶。

这对 $P=31,32$ 的边界非常重要。

9. 复杂度重新估计

令：

P=\sum_C\max(0,D_C).

我们已经有：

P\le 32

才需要真的算。

每个正 excess 块的关联二分图环秩为：

\mu=D+1.

压 2-core 后，度 $\ge3$ 的核心点数量是：

O(\mu).

长链、树枝全部通过剥离 DP 吸收到点权里，不再参与指数递归。

递归分支每次都会：

删除一条核心边，降低环秩；
或删除两个核心点，并触发 2-core 剥离，通常降低更多环秩。

实际边界可以按：

T(\mu)\approx T(\mu-1)+T(\mu-2)

估计。

但由于 $P=33$ 已经直接为 $0$ ，真正需要处理的最大值是：

\mu\le 32.

于是指数部分从原来的极限 $\varphi^{34}$ 下降到近似：

\varphi^{32}\approx 5.7\times 10^6.

更重要的是，每个递归节点处理的是压缩后的核心，而不是 $2\times 10^5$ 级别的大图。

10. 你现在的代码应当怎么改

不是小修，而是要重写 solve_bgraph()。

旧结构：

cpp
solve_bgraph:
    simplify isolated vertices
    split components
    cactus_dp
    branch

新结构必须是：

cpp
solve_bgraph:
    reduce_to_2core_with_weights
    split core components
    cactus_dp_with_weights
    branch_with_block_weight

核心差别是：

cpp
degree-1 vertex must not branch recursively;
degree-1 vertex must be absorbed into neighbor weights.

这是性能能不能过的分水岭。

11. 我建议下一份代码按这个顺序写

先不要直接写全量优化版。建议分三步：

写 weighted monomer-dimer 基础框架
每个点维护 free[v] 和 block[v] 两个多项式。
实现 2-core 剥离
先只测树和基环树，确保结果和旧代码一致。
再接 cactus + 非 cactus 分支
分支后必须重新跑 2-core 剥离。

这样对拍会很清楚。

最关键结论：

上一个方案炸，是因为它没有把度 $1$ 链作为 DP 消掉。
正确方向是：关联二分图 + 点权 monomer-dimer + 每轮递归前压 2-core。
另外 $P=33$ 可以直接返回 $0$ ，这会干掉最极限的 $D=33$ 卡法。

Câu hỏi

Python

Python

Python

Python

Python

Suy nghĩ

Trả lời

1. 对每个连通块求多项式

2. 复杂连通块的 DP 状态

3. 转移

3.1 删除这条边

3.2 保留边，并选择端点 uuu

3.3 保留边，并选择端点 vvv

4. nice tree decomposition 版本

introduce vertex

forget vertex

introduce edge

join

5. 为什么这严格等价于你的权值公式

若 KKK 是树

若 KKK 是基环树

若 KKK 有两个及以上环

6. 复杂块为什么能过

7. 最终算法框架

Câu hỏi

Suy nghĩ

Trả lời

1. wH≤μH+1w_H\le \mu_H+1wH​≤μH​+1 的证明

2. 复杂连通块 DP 的完整模型

3. DP 状态

4. Leaf 节点

5. Introduce vertex 转移

6. Forget vertex 转移

7. Introduce edge 转移

7.1 删除这条边

7.2 保留这条边，并选择端点 uuu

7.3 保留这条边，并选择端点 vvv

8. Join 转移

9. Root 答案

10. 正确性说明

11. 复杂度

Câu hỏi

Python

Python

Python

Python

Suy nghĩ

Trả lời

1. 关键转换：复杂块改成匹配多项式

2. 关联二分图的环秩很小

3. 子问题定义

4. 基本化简

4.1 空图

4.2 孤立右点

4.3 孤立左点

4.4 不连通图

5. 森林与仙人掌作为多项式时间基底

6. 核心分支递归

情况 1：不使用匹配边 eee

情况 2：使用匹配边 eee

7. 为什么复杂度是 φμ\varphi^\muφμ

7.1 删除边分支

7.2 使用边分支

8. DP 多项式转移细节

8.1 孤立左点

8.2 不连通图合并

8.3 分支合并

9. 这个模型为什么等价于复杂块计数

10. 最终复杂块算法

11. 总复杂度

12. 这个方案相对之前的优势

Câu hỏi

Suy nghĩ

Trả lời

Câu hỏi

Suy nghĩ

Trả lời

为什么这个 gen 能卡边界

建议你这样卡

3.2 保留边，并选择端点 $u$

3.3 保留边，并选择端点 $v$

若 $K$ 是树

若 $K$ 是基环树

若 $K$ 有两个及以上环

1. $w_H\le \mu_H+1$ 的证明

7.2 保留这条边，并选择端点 $u$

7.3 保留这条边，并选择端点 $v$

情况 1：不使用匹配边 $e$

情况 2：使用匹配边 $e$

7. 为什么复杂度是 $\varphi^\mu$