题解：P12445 [COTS 2025] 数好图 / Promet

· · 题解

[COTS 2025] 数好图 / Promet

有点厉害的数数题。

可以发现 k=0 的答案和 k=2 的答案是相同的，为了防止 corner case 直接不考虑 k=0 的求解。

称满足存在 1\rightarrow u 和 u\rightarrow n 的点构成的 DAG 称为主 DAG。首先考虑主 DAG 上的点满足什么性质，只保留主 DAG 上的点后 1 号点必有出度，n 号点必有入度，其余点必定有入度和出度。

那么此时 k=n 的情况就很好做了。考虑钦定必有出度，容斥入度。设 f_{i,j} 表示前 i 个点，钦定了有 j 个点入度为 0，转移时考虑当前点有没有钦定入度，转移乘个系数即可。最后可以对于每个 n 用二项式反演求出 k=n 的答案。需要注意因为 1 号点必定没有入度所以最终容斥时要钦定最后一个点必选（具体见代码）。

那么现在我们可以对于任意 k 确定其主 DAG 了，考虑将剩下的点挂上去。

考虑对剩下的点分为 1 号点能到达和 1 号点不能到达两类。称主 DAG 上的点为 1 类点，剩下点中 1 号点可到达的点为 2 类点，剩下点中 1 号点不可达的点为 3 类点。

考虑不同点之间的连边。

  1. 由于 $3$ 类点不能从 $1$ 号点到达，而 $1$ 类点可以从 $1$ 号点到达，所以 $1$ 类点不能连 $3$ 类点，因此 $1$ 号点可以连 $1,2$ 号点。
  2. 因为其不在主 ```DAG``` 上又能从 $1$ 到达，所以其不能到达 $n$，只能连 $2$ 类点。 同时由于该类点的定义，**必须有至少一个 $1$ 类点或一个 $2$ 类点与其相连**。
  3. 其可以连向任意点，因为其不可以从 $1$ 号点到达，所以连不连没有影响。

由于主 DAG 上的点（即 1 类点）之间的连边已经被确定，所以只需要考虑其它种类的连边。设 g_{i,j,k} 表示前 i 个点，有 j 个 1 类点，k 个 2 类点。转移考虑当前点是哪一类，根据上面的连边方式转移即可，时间复杂度 \operatorname{O}(n^3)。

考虑优化。可以发现对于 3 类点其实不在意可以连接的 1 号点和 2 类点分别有多少个，只关心其总共有多少个。于是重新设计状态，设 g_{i,j} 表示前 i 个点有 j 个 1 类点，其它都是 2 类点的连边方案。设 h_{i,j} 表示前 i 个点，有 j 个3 类点的方案。最终枚举得到 1，2，3 类点分别有多少个，乘上系数即可。时间复杂度 \operatorname{O}(n^2)。

细节比较多，具体可以见代码。

code