网上的唯一一篇题解写的就是屎,还有一堆错误 /fn。
来发篇自己理解的题解,可能有问题,可能是我犯唐了 /dk。
考虑 sub3 的特殊性质 \(q_i=i\) 怎么做:
发现对于一个前缀 \(p[1 \sim i]\),且值域上恰好对应 \(1 \sim i\) 即 \(\max_{1 \le j \le i} p_j=i\),可以直接对 \(1 \sim i\) 排序会满足 \(q\) 前 \(i\) 项的限制。而且如果有两个满足该条件的前缀 \(1 \sim i, 1 \sim j(i \le j)\),那么对 \([1,i]\) 排序,\((i,j]\) 也是一个 \((i,j]\) 值域上的排列,也对 \((i,j]\) 排序,也会得到排列 \(q\) 的前 \(j\) 项。
由于 \(k\) 越小,答案字典序单降。所以我们应该尽可能让段数更多。因此我们对极小的段的个数 dp。设 \(f_{i,j}\) 代表前 \(i\) 个数划分成了 \(j\) 个极小段的方案数。答案即为 \(\sum_{k \le i \le n} f_{n,i}\) 对于 \(j \ge 1\),枚举最后的一个极小段长度 \(k\),有转移:
考虑 \(f_{i,0}\) 怎么算,考虑对于一个 \(1 \sim i-1\) 的排列,插入 \(i\),找到第一个满足上面条件的前缀 \(j\),那么 \(j\) 前面必须插入一个 \(i\)。则有转移:
接下来考虑正确做法:我们记满足 \(q_{i-1}>q_i\) 的点为一个断点。
考虑 \(f_k(p)\) 是怎么生成的,在 \(i \in [1, n-k]\) 选出一个最小值,删除它,得到 \(q_1\),继续这个流程得到 \(q_{2,3...}\),直到选中 \(n-k\)。按照上面的分段思路,很容易可以得到,\(1 \sim i\) 可以划分为一段的条件是 \(\{q_1,q_2,...,q_i\} = \{p_1,p_2,...,p_i\}\)。
我们记 \(q\) 的第一个断点为 \(t\),第二个断点为 \(t'\),那么有以下结论:
由 \(q\) 生成的 \(p\) 的形态如下:
\([1,t)\) 被划分成若干段,\([t,t')\) 整体成一段,并且如果 \(t'>t+1\),则有 \(\min_{t \le i \lt t'} p_i\) 位于 \(t'-1\) 且 \(q_{t+1}>q_{t-1}\),然后 \([t',n]\) 每个数字单独成一段。
一个简要的证明:
\([t,t')\) 单独成段的意义在于,可能会刚好把最小值卡在最后一个并且 \(k\) 刚好要求最小值独立成段,例如 \(q=[1,3,2,4,5,7,6],k=4\),一种存在的 \(p=[3,1,5,4,2,7,6]\)。如果最小值不在 \([t,t')\) 的末尾,完全可以把最后一个数单独裂出去,答案更优。如果不满足 \(q_{t-1}<q_{t+1}\),把 \(q_t\) 或者 \(q_{t+1}\) 合并到前面,答案更优。
那么枚举 \(t'\),答案即为 \(\sum_{t'}f_{t-1,k-(n-t'+2)}(t-t'-1)!\),时间复杂度 \(O(n^3)\)。