F. Chain Prefix Rank

前置：广义串并联图方法，平衡树。

鉴于笔者也没学过这种高科技，本题解简述广义串并联图的基础，所以不用担心看不懂。

题意

给定一棵

n

个点的树和一个长度为

n

的数组

a

，求有多少长度为

n

的排列

p

，满足对于每个

u

恰有

a_u

个祖先

v

使得

p_v<p_u

。答案对

998244353

取模。

数据范围：

对于 F1： $\sum n\le 5000$ 。
对于 F2： $\sum n\le 5\times10^5$ 。

做法

看了无数篇 blog，所以没法列举出处了，因为我也不知道我在默写哪篇。如果你发现我大篇幅默了某篇你可以来找我。

这里讲官解做法。

我们引入广义串并联图的概念。

广义串并联图基础

定义

如果一个无向图中不存在四个点，使得这四个点间两两有路径相连，且路径间互不相交，则这个图被称为广义串并联图。树和仙人掌是常见的广义串并联图。

构造

一个两个点、一条边的无向图是一个广义串并联图。为了方便，我们为每个广义串并联图定一个源点和一个汇点。
将两个广义串并联图串联，即将其中一个的源点与另一个的汇点合并，得到的新图也是广义串并联图。该图源点为汇点被合并图的源点，汇点为源点被合并图的汇点。
将两个广义串并联图并联，即将两图的源点和汇点分别合并，得到的新图也是广义串并联图。合并后的源汇点即为新源汇点。

性质与判定

口诀：删一缩二并重边。

即广义串并联图可以经过若干次下面三种操作变成一个点：

删一度点：删掉一个度数为 $1$ 的点。
缩二度点：若有边 $(u,v),(v,w)$ ，则将其合并为一条边 $(u,w)$ 。
合并重边：将重边合并。

上述性质也可以用于判定。

上述性质中，由于这些操作通常容易合并信息，我们在操作的过程中可以在点上和边上维护信息以方便地进行统计。

更一般地，对于点数和边数相差较小的图，对其也进行上面的操作直至无法操作，可以将其剩余的点数和边数缩到可以暴力的范围，这种方法叫广义串并联图方法。设

m-n=k

，则最终得到的图有

n\le 2k,m\le 3k

。

本题

首先

a_i

实质上就是

i

在其到根路径上的 rank。

所以为了找到排列我们可以考虑从根向下不断地在当前路径上插入点。我们建一张表示这个关系的图，为了确保每个点都能插入，我们在

1

的上方建立点

n+1

，在

n+1

的上方建立点

0

，则此时初始的图就是一个

0\to n+1

的边。插入点

1

时，增加

0\to 1

和

1\to n+1

的边，以此类推。

这样得到的图视为无向图后显然是一个广义串并联图（因为插入的点可以“缩二度点”后“合并重边”来删掉），题目要求其拓扑序个数。很多题解里这里直接给的总式子，我简单展开一下。我们在边上维护信息，下设

f_{x,y}

为边

(x,y)

中包含的方案数，

sz_{x,y}

为边

(x,y)

中包含的点数。

缩二度点（左上图）：两边的相对顺序固定所以方案直接相乘，点数加上删掉的点即可。有方程 $f_{u,w}=f_{u,v}f_{v,w},sz_{u,w}=sz_{u,v}+sz{v,w}+1$ 。
合并重边（左下图）：两边的相对顺序不固定，只需要确保内部顺序，所以方案相乘后应该加上安排点的位置的一项。点数直接相加。有方程 $f_{u,v}=f_{u,v}f'_{u,v}\text{C}_{sz{u,v}+sz'{u,v}}^{sz_{u,v}},sz_{u,v}=sz_{u,v}+sz'{u,v}$ 。
总式（右图）：其实就是一次缩二度点一次合并重边，所以直接将合并重边式子中 $f'$ 和 $sz'$ 全文替换成缩二度点的式子即可。有总方程 $f_{u,w}=f_{u,w}f_{u,v}f_{v,w}\text{C}_{sz{u,w}+sz{u,v}+sz{v,w}+1}^{sz_{u,w}},sz_{u,w}=sz_{u,w}+sz{u,v}+sz{v,w}+1$ 。

上述过程暴力实现是

n^2

的，平衡树维护一下前驱后继可以

1\log

。

题解 CF2164F1 Chain Prefix Rank (Easy Version)

文章操作

F. Chain Prefix Rank

题意

做法

广义串并联图基础

定义

构造

性质与判定

本题

相关推荐

评论

题解 CF2164F1 Chain Prefix Rank (Easy Version)