CF1806D 题解

masonpop · 2023-07-24 18:14:00 · 题解

CF *2500，难度貌似只在题意理解。做法貌似比较固定，语言描述部分参照官方题解。

注意洛谷翻译有误，以下是真实题意。

对于排列 \{p_1,p_2,\cdots p_{m-1}\}，我们考虑每个 i，如果 a_{p_i}=0，那么我们从 p_i+1 所属连通块的根向 p_i 所属连通块的根连边，否则反过来。定义每个连通块的根是那个所有点指向的点（即出度为 0 的点，这个确实有点像并查集）。定义这个排列的贡献为操作结束后点 1 的入度。对于每个 k ，k=1,2,\cdots n-1，分别求所有长度为 k 的排列的贡献和。

记一次操作为 (p_i,a_{p_i})。考虑什么样 (x,a_x) 的操作能对 1 的入度产生贡献。容易发现，这次操作产生贡献的条件是 a_x=0 并且 1 至 x-1 均在这次操作前出现，即 1 与 x 已经联通。我们可以只考虑涉及 x 的连通性的操作。

由此就可以设计 dp 状态了。设 f_i 表示长度为 i，且操作完后 1 至 i+1 的节点联通的排列个数。我们考虑新加入的操作 (i,a_{i}) 的位置：若 a_i=0，则不管加到哪里都不会影响 1 的出度为 0。否则，容易发现当且仅当其放到最后一个位置时会影响 1 树根的地位，也只有这个位置不合法。因此，当 a_i=1 时，f_i=f_{i-1}\times (i-1)。否则，f_i=f_{i-1}\times i。

接下来统计答案就轻而易举了。设 g_i 表示所有长度为 i 的排列的总贡献。容易发现操作 (i,a_{p_i}) 的加入不会影响前面操作的贡献。而且，当且仅当其放在最后一个位置且前面 i-1 次操作已经让 1 成为了根。因此，g_i=g_{i-1}\times i+[a_i=0]\times f_{i-1}。

时间复杂度 O(n)。代码。