DAG上容斥

如果你是先看题解再做题，自然地接受了这一套路的话，那你很难想象这为什么是黑题。

[ABC306Ex] Balance Scale

给定一个无向图，你需要把每条边定为 $>,<,=$ 中的一个，使得图不出现矛盾，对方案计数。

$n\le 17$ 。

首先考虑没有 $=$ 的情况，你发现只有大于小于还不矛盾等价于有向且无环，所以就是要我们做一个 $\text{DAG}$ 计数。

那咋计数呢，考虑拓扑排序的时候会脱掉一层叶子，我们枚举这些没有入度的点，这些点间不能有边。

设 $f_S$ 表示 $S$ 集合是 $\text{DAG}$ 的方案数， $[T]$ 表示 $T$ 是独立集，则转移式：

$f_S\gets \sum_{T\sube S,T\ne\varnothing,[T]}f_{S\setminus T}$

先别急着喊就这，你仔细想想发现会算重，更具体的说，每个独立集的子集都是独立集，所以这种合法方案会被每个子集各算重一次，真实的有 $r$ 个叶子的方案会被统计重 $2^r$ 次，它们杂糅在一起，难以分开。

这让我们想到容斥，考虑在 $r\bmod 2=1$ 时加上该方案，在 $r\bmod 2=0$ 时减去该方案，这样根据容斥原理，由于不存在 $r=0$ 的情况，每个方案都只会被统计恰好一次。

用容斥原理可以得到：

$f_S\gets\sum_{T\sube S,T\ne\varnothing,[T]}(-1)^{|T|+1}f_{S\setminus T}$

接下来考虑加上等号，其实就是允许选非独立集了，但每个连通块必须视作一个点，转移式与刚刚是一样的，只是改变了指数的奇偶性而已，正确性的论证也是相同的。

P10221 [省选联考 2024] 重塑时光

小 T 正在研究某段时间中所发生的事件。经观测，有 $n$ 个编号为 $1\sim n$ 的事件在这段时间内按顺序依次发生，第 $i$ 个发生的是事件 $p_i$ 。这个描述事件发生顺序的排列 $p$ 可称为这段时间的时间线。

突然，邪恶生物小 S 攻击了这条时间线，将这 $n$ 个事件的发生顺序 $p$ 变为了在所有长为 $n$ 的排列中等概率随机选取的一个排列。不仅如此，小 S 还用剪刀把时间线剪断，通过进行 $k$ 次操作，将排列 $p$ 分割成了 $(k + 1)$ 段。

具体而言，在小 S 进行第 $i$ 次操作时，排列 $p$ 和之前所有插入的剪断点构成了一个长度为 $(n + i - 1)$ 的序列。该序列包括所有相邻元素之间和序列开头、末尾处共有 $(n + i)$ 个插入位置。小 S 将从这些插入位置中等概率随机选取一个位置，插入一个新的剪断点。最后，小 S 从最终被插入的 $k$ 个剪断点处把序列剪开，将排列 $p$ 分割成了 $(k + 1)$ 段序列。这 $(k + 1)$ 段序列中可能有空序列。

为了拯救这条即将毁灭的时间线，小 T 决定把这 $(k + 1)$ 段序列按某种顺序重新拼接成一个长度为 $n$ 的排列，形成一条新的时间线。不过，由于事件之间存在一定的逻辑关系，事件的发生时间之间也存在一些先后顺序要求。经研究，共存在 $m$ 条先后顺序要求 $(u, v)$ ，要求事件 $u$ 的发生时间必须在事件v 之前。也就是说， $u$ 在时间线中的出现位置必须在 $v$ 之前。

请你设计程序，计算有多大的概率，存在至少一种重新排列这 $(k + 1)$ 段序列，并将其重新拼接为一条新的时间线的方案，能够使所有的 $m$ 条事件发生时间之间的先后顺序要求都得到满足。

为了避免精度误差，请你输出答案对 $10^9 +7$ 取模的结果。形式化地，可以证明答案可被表示为一最简分数 $\frac{p}{q}$ ，请你输出一个 $x$ 满足 $0 \le x < 10^9+7$ 且 $qx \equiv p \pmod {10^9+7}$ 。可以证明在题目条件下这样的 $x$ 总是存在。

$n,k\le 15$ 。

题意难以概括，直接扔上来吧。

发现 $k=0$ 是 $\text{DAG}$ 拓扑序计数（我考场上竟然没想出来状压），考虑状压，设 $g_{S}$ 为 $S$ 中的点是拓扑序的前 $|S|$ 个的拓扑序方案数，转移就是再选一个点，这个点要满足所有指向它的点都已经被选了。

我们先做一些基础的转化，我们可以先求出 $\mathbb N\cap[1,n]$ 划分成 $i$ 个非空集合的答案 $f_i$ ，最后再把这些集合以任意顺序组合（在 $f$ 中需要统计每个集合内部的拓扑序 $g_S$ ），由于空集合是彼此之间没区别的，所以最后再把空集合插到空隙中，也就是：

$\text{ans}\gets\frac{\sum_i\binom{k+1}{i}f_ii!k!}{n!\prod_{i=1}^k(n+i)}$

接下来只需要求 $f_i$ 即可。

复用记号，设 $f_{i,S}$ 表示 $|S|$ 中的点划分成了 $i$ 个集合的方案数，你发现这其实就是要做 $\text{DAG}$ 计数，也就是上面的那个题，每次剥掉一层叶子（注意 $\text{DAG}$ 上每个元素都是一个集合）。

由于每段元素（每个集合）可以内部解决，设 $v_{i,T}$ 为 $i$ 个集合组成 $T$ 的内部拓扑序方案和。

转移式：

$\begin{aligned}v_{i,S}&\gets\sum_{\min S\in T\sub S} v_{i-1,S\setminus T}g_{T}\\f_{i,S}&\gets\sum_{j}\sum_{T\sube S,T\ne\varnothing}(-1)^{j+1}v_{j,T}f_{i-j,S\setminus T}\end{aligned}$

$\Theta(3^nn^2)$ ，常数比较小。

冷静一下发现 $g$ 的定义有问题，你发现 $g$ 只能求出原图结构存在时的拓扑序数量，也就是说只有 $g_{[1,n]}$ 这个值是正确的，我们看我们的转移式发现我们是想要“生成”一个 $\text{DAG}$ ，于是我们每次加点的时候的条件是该点出边没有被选，而不是该点入边全部被选。

此外被我忽视的一点是： $v$ 合并时两个集合不能有边，即我们还是要做一个独立集问题。

并且 $f$ 在合并 $T$ 时需要保证剩下的点到 $T$ 没有边，以上两点可以通过维护一个 $\text{out}_x$ 表示 $x$ 集合中的点的出点集合来保证。

记得枚举到 $\text{popcnt}(x)$ 停下，会快不少。

考场上需要比较冷静才能想出来，这也是我要努力的方向了。