P4566 [CTSC2018] 青蕈领主

251Sec · 2024-08-20 21:04:32 · 题解

终于会全在线卷积了。

把所有区间 [i-L_i+1,i] 画出来，手玩发现如果存在两个区间相交但不包含那就无解，而且如果 L_n \ne n 也无解。

否则可以把区间画成一个树形结构，对于树上每个点考虑它的填数方案，发现可以把它的每个儿子缩成一个点考虑，那么我们只需要解决这样一个子问题：形如 L=\{1,1,1,\cdots,n+1\} 的方案数计数，设这个方案数为 f(n)。我们需要对所有 n \le 5 \times 10^4 求出 f(n)。

人类智慧地，在逆排列上考虑，相当于求长度为 (n+1) 的排列，使得所有不包含最大值的区间都不连续。考虑加入最小值 1 并把加入前的所有数加一，讨论加入最小值前序列的情况：

• 加入前序列合法，则最小值只要不放到次小值旁边就行，方案数 (n-1)f(n-1)。
• 加入前序列不合法，则加入前只能存在一段极长不合法区间，枚举这段区间的长度 i。
  • 首先这段区间原先的最小值不能是 1，否则加入后整个区间仍然连续，然后在这个限制下原区间和 1 一起的方案数应当为 f(i)，即把原来的元素从小到大标号为 1 \sim i，再把加入的 1 视为 (i+1)。
  • 这段区间的值域有 (n-i-1) 种选择方法（即不能包含 1 和 n）。
  • 然后把这段区间看成整体，并把它按照去掉 1 之后任意元素在排列里的大小关系标号，因为这段区间去掉 1 之后是连续的所以这样的标号方法良定义。因为我们钦定了这个区间是极长的，因此它也拥有不能往外延伸连续不包含 (n+1) 区间的性质。这和原问题完全等价，于是这里的方案数为 f(n-i)。
  • 乘起来，方案数为 (n-i-1)f(i)f(n-i)。

于是我们得到递推式：

（为了让这个式子比较好看，我们翻转了右边求和的下标）

这是全在线卷积的形式，即形如 c=a*b 的问题，其中 a,b 都需要在线得出。

考虑这种问题的处理方法：不妨设要求 0 \sim n 的 f，令 m=\left\lfloor\frac{n}{2}\right\rfloor。假设我们已经求出了 0 \sim m 的 f，考虑对后面的贡献，设它从 a_ib_j 得到。

我们知道半在线卷积可以简单地在 O(n \log^2 n) 复杂度内求解，则 T(n)=T\left(\frac{n}{2}\right)+O(n \log^2n)，由主定理立得总复杂度为 O(n\log^2 n)。

上述算法的暴力卷积实现，80pts。可读性应该挺强的。

NTT 实现，100pts。