题解：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

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

文章操作

[COTS 2025] 数好图 / Promet

相关推荐

评论

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