题意

给出 $n$ 个点 $m$ 条边的无向图 $G$，长度为 $n$ 的上界数组 $(ci{r}_1,\dots ,ci{r}_n)$，以及异或和 $C$，求满足以下条件的数组 $(a_1,\dots ,a_n)$ 的数量（对 $998244353$ 取模）：

• $0\le a_i\le ci{r}_i$（$\forall 1\le i\le n$）；
• 对于每条边 $(u,v)$，$a_u\ne a_v$；
• $a_1\oplus a_2\oplus \cdots \oplus a_n=C$，其中 $\oplus$ 代表异或。

数据范围：$n\le 15$，$m\le \frac{n(n-1)}{2}$，时限 4s，空间 1G。

• 部分分 $m=0$。
• 部分分 $n\le 13$。

Keywords & Evaluation

::::info[Keywords] 容斥、生成子图、异或、轮廓线、数位dp ::::

$\text{Difficulty : AT 2900 | (6+)}$

$\text{Quality : A-}$

Solution

$m=0$ 的子问题

先考虑 $m=0$ 的情形：求若干个 $a_i\in [0,ci{r}_i]$ 异或起来恰好为 $C$ 的方案数。

直接数位 DP：从高位开始扫，记录 $state$ 表示哪些数在当前位仍然顶满了 $ci{r}_i$，状态数 $2^n$，虽然能过这个部分分，但不太够用。

考虑优化。注意到只要 $state$ 中有某个数不再顶满高位限制，那么它在接下来的低位就可以在 $[0,2^k)$ 中随便选——也就是说，其他位可以开摆了！无论其他位置怎么选，它总有一种唯一取法把后面剩下的位异或成想要的 $C$。于是我们枚举第一个出现"不满"的位（即高位处已经比限制小），以及是哪个数在该位首先“不满”，在每位做一次 $O(n)$ 的 DP 来钦定第一个。整个子问题可以在 $O(n\log w)$ 内解决。

于是我们可以快速求出形如“求若干个 $a_i\in [0,ci{r}_i]$ 异或起来恰好为 $C$ 的方案数”。

---

互不相同的容斥

现在回到"互不相同"的限制。

你听说过 ABC236Ex 吗？如果你听说过你应该知道接下来要干什么：

把"互不相同"容斥成"钦定相同"。钦定一个边集 $E$ 中的边两端取值相同，显然容斥系数为 $(-1{)}^{|E|}$。

我们只关心 $E$ 构成的连通块（等于的传递性）：每个连通块内部取值相同，块的上界取块内所有 $ci{r}_i$ 的 $\min$（必须全满足）。不同连通块之间独立，等价于 $m=0$ 的子问题。

此外：

• 奇数大小的连通块：其异或贡献就是取值 $a_i$（受 $ci{r}_i$ 约束）；
• 偶数大小的连通块：偶数个相同值异或恒为 $0$，对异或和没有贡献，直接不考虑。

---

容斥系数 $G(S)$

设 $G(S)$ 表示点集 $S$ 的容斥系数，即在 $S$ 内部选边集 $G(E)$ 使 $S$ 连通的 $\sum (-1{)}^{|E|}$。

这个是经典的“任意-连通”的单步容斥。

先看不要求连通的情况：在 $S$ 内部随便选边，容斥系数之和为 ${\sum }_{E\subseteq E(S)}(-1{)}^{|E|}=(1-1{)}^{|E(S)|}$。

当 $|E(S)|\ne 0$ 时这个和为 $0$。

于是用单步容斥求 $G(S)$：我们已知任意情况下 $S$ 的系数之和，我们想求出 $S$ 是一个连通块的情况下的系数之和，于是我们减去 $S$ 是不止一个连通块的情况，即 $S$ 由若干个连通块组成：

固定 $S$ 中编号最小的点 $u$，枚举它所在的连通块 $T$（$u\in T$,$T\subset S$），其他部分不要求任何连通性，

$$G(S)=[|E(S)|=0]-\sum _{\begin{array}{c}T\subset S,T\ne \varnothing \\ \min (S)\in T\end{array}}G(T)\cdot [|E(S\setminus T)|=0]$$

这本质是子集幂级数的"子集 $\ln$"：连通结构由若干不连通块无序组合而成。

---

DP 与状态设计

在处理完容斥系数后，我们现在变成这样一个问题：把图分成若干个连通块，这个过程会产生 $\prod G(S)$ 的系数，然后关心每个奇数连通块的最小值 $cir$ 构成的可重集合。

DP 中我们只需要关心最终哪些点成为了奇数大小连通块的最小值，因为只有它们才对应 $cir$ 限制，偶数连通块直接乘上 $G$ 的系数乘最小值就行。

令 $F(S_1,S_2)$ 表示：已经考虑了 $S_1$ 中的点，其中 $S_2\subseteq S_1$ 是作为奇数大小连通块最小值的点集。

转移时考虑 $S_1$ 的一个子集 $T$ 是某一个连通块，设 $u=\min (T)$：

• 若 $|T|$ 为奇数：$u$ 必须属于 $S_2$，贡献 $G(T)$；
• 若 $|T|$ 为偶数：连通块可取 $[0,ci{r}_u]$ 中任意值，贡献 $G(T)\cdot (ci{r}_u+1)$。

即

$$\begin{array}{rl}F(S_1,S_2)=\sum _{\begin{array}{c}T\subseteq S_1,|T|\equiv 1(\mathrm{mod}2)\\ u=\min (T),u\in S_2\end{array}}& F(S_1\setminus T,S_2\setminus \{u\})\cdot G(T)\\ +\sum _{\begin{array}{c}T\subseteq S_1,|T|\equiv 0(\mathrm{mod}2)\\ u=\min (T)\end{array}}& F(S_1\setminus T,S_2)\cdot G(T)\cdot (ci{r}_u+1)\end{array}$$

设 $U$ 为全集。对每个 $S\subseteq U$，将 $F(U,S)$ 中 $S$ 对应的点（奇数连通块）代入 $m=0$ 子问题计算方案数，乘上系数累加即得答案。

这部分复杂度 $O(4^n+2^n\log w)$，能过 $n\le 13$。适当剪枝其实也能冲 $n\le 15$——因为只有奇数连通块的最小值才有用，实际状态远少于 $4^n$。

考虑如何做的更快一些：这个题似乎很难直接上 FMT/FWT，常见子集幂级数相关科技也难以进一步降低复杂度，所以换个角度：从"最小值"入手优化。

---

更改 DP 顺序

类似轮廓线 DP，按 $a_u$ 从小到大枚举 $u$，每次加入一个以 $u$ 为最小值的连通块。

• 此时编号 $<u$ 的点已经都考虑过了，不会再加入 $S_1$，只需要记录它们是否在 $S_2$ 中。

• 编号 $>u$ 的点只需记录是否已在 $S_1$ 中（它们就算在 $S_1$ 里，其也不可能属于 $S_2$，因为它们不可能是最小值，我们目前只考虑了最小值 $\le u$ 的 block）。

于是每个点有三种状态，总状态压到 $O(3^n)$。按顺序枚举 $u$，枚举以 $u$ 为最小值的集合 $T$（$T$ 中其余点编号 $>u$）进行转移即可。时间复杂度 $O(3^n\cdot n+2^n\log w)$，于是我们做完了这个题。

其实这个东西从轮廓线的角度来看其实本质就是在对这个子集幂级数做一个逐点的牛顿迭代，如果你阅读集合幂级数神秘科技 此间最是少年意难断 你应该可以把这一步的优化一脚踹死。