AtCoder - 3962 Sequence Growing Hard
2021-04-09 03:24
186248260 第一部分：模型构建。 考虑 a[i][] 和 a[i-1][] 第一个不一样的位置j (为了方便视 a[i-1][i] = 0)，显然a[i][j] > a[i-1][j]，不然字典序就更小了。 我们接着转化模型，设j是最小的满足 a[i][k] != a[i-1][k] 的k，那么我们可以把第i次操作看成 在a[i-1][j] 前面挂了一个新的数 a[i][j] (要求 a[i][j] > a[i-1][j]),从而使a[i-1][j] 位移到了 a[i][j+1]。 第二部分：高效求解问题。
最近的一场AGC的题目(1200分题！！)，当时比赛的时候一直怼这个题没怼出来QWQ，之后只做了前三个题QWQ(这样也能涨rating???)，后来回想了一下，搞了半天才搞出来。
因为这个题目实在是不错，所以我会尽力写好完整的题解的hhhh
稍微想想就可以知道，第i行肯定是在第i-1行的基础上再插入一个数字得来的，并且要求字典序更大。
但是稍不留神就会算重，比如 在 1,3,3,2 的两个3后面插入3，得到的新的序列是一样的。
那么在不考虑容斥的情况下，我们如何去构造出 不重复 且满足字典序更大 的计算方案呢？
并且很容易想到，如果两个 a[i][] 的 j不一样，那么它们肯定是不同的，所以我们现在就找到了一种不会算重的方案。
于是我们就可以把第i次操作加入的点 抽象成一棵节点带权的有根树的节点(初始只有0节点，且权值是0)，一次操作就相当于在某一个节点下挂一个新的权值大于它的节点(对应在原序列某个数前面挂数)。
问题就转化成了，问有多少颗节点数为 n+1 的有根树，儿子的编号都小于爸爸，权值都大于爸爸，并且根的权值是0(对应第一次操作可以加入任意[1,k]的数)。
不难想到设 f[i][j] 为 有i个节点，且根的权值是j的有根树的方案数，但是转移不是很好想的样子。。。
我们先钦定这棵树内的节点编号是1~i，那么转移就可以写成： f[i][j] = ∑ C(i-2,u-1) * f[u][k] * f[i-u][j] (k>j)
这就相当于枚举，和2节点在一颗子树内的分别是哪些点，这颗子树的方案和剩下的点的方案(依然是以1为根，只不过节点数变成了i-u)。
文章标题：AtCoder - 3962 Sequence Growing Hard
文章链接：http://soscw.com/index.php/essay/73148.html