求字典序第 k 小方案类问题
昨天在模拟赛里面遇到了一个需要求字典序第 \(k\) 小的方案的题目。
虽然有点思路和方向但是并不清楚，想起来这样的题应该还不少，随开本文作一个记录。
如果硬要说泛化，除掉字典序 k 小路径那样的东西，应该大多都是，考虑算方案数，argue 一下每个位置/每一段/某一个后缀怎么填，一般来说你能知道一整个前缀的方案，然后计算贡献的时候考虑变化在这一位的贡献，大概就是这样。
算方案一般是比较难的部分，这种思想可能和康托展开差不多。
求字典序第 k 小的合法括号序列ψ(｀∇´)ψ
首先合法括号序列计数显然大家都会；
对于长度为 \(2n\)，\(m\) 种括号，合法括号序列数为：
可以注意到这个的数量级很大，我们假设我们使用的 C++ 是 C++ with BigIntegers，再考虑接下来的问题。
然后我们规定 ( 的字典序小于 )，对于其它括号类似定义，不过这里先只考虑 \(m = 1\) 的情况。
构造一个合法括号序列是容易的，构造字典序第 \(k\) 大的括号序列显然也是容易的，但是把这两个限制拼起来，肉眼可见的难做，至少说稍微想想没什么好的办法。
但是我们不难想到，因为 \(n\) 小的时候合法方案数也会少，我们能不能考虑，知道了某个前缀的方案数，在后面拼接一些合法的括号序列，使得它恰好能满足排名为 \(k\) 的要求？
乍一看是挺对的，但是很可惜，合法括号序列的一个前缀并不一定是合法括号序列，我们没有办法这么做。
所以我们还是先老老实实按位确定吧，考虑一下每一位是放左括号还是右括号，并考虑这会增加多少个字典序小于我们要求的序列的合法括号序列（虽然是合法，不过我们根据字典序的定义，此时已经如果有一个前缀已经满足了，后面我们就不用管了）
左括号显然不会对这个值产生影响，于是我们只需要考虑放右括号的情况。
考虑在位置 \(i\) 放右括号，首先之前已经小于 \(s\) 的序列 \(p\) 已经被我们计算过了，我们只需要考虑这一位带来的变化。
换句话说我们此时统计的是，\(p_{i} = \texttt{(}\) 的方案，可以发现这样的 \(p\) 一定满足 \(p[1..i-1] = s[1..i-1]\)。
于是我们后面 \(2n - i\) 个位置不管怎么放，只要让 \(p\) 合法即可。
于是我们统计，\(p[1..i-1]\) 中有多少个左括号还没有被匹配（显然不可能有右括号没有匹配），记为 \(t\)。
然后我们只需要让 \(p[i + 1, 2n]\) 为一个，包含 \(t\) 个恰好没匹配的右括号，左括号全部匹配的括号序列就行了。
后面这个东西可以通过一个 \(O(n^2)\) 的 DP 进行统计，具体来说设 \(dp(i, j)\) 表示，考虑长度为 \(i\)，有 \(j\) 个恰好没匹配的右括号且左括号全部匹配的括号序列数量。
考虑新一位放什么，可以得到转移：\(dp(i, j) = dp(i - 1, j - 1) + dp(i - 1, j + 1)\)，听说也可以看作二维平面上行走的一个问题。
当然，通过这个，我们也可以计算任意一个合法括号序列的排名，甚至可以扩展到多种括号，我们只需要类似考虑即可。
回到正题，考虑每一位会导致什么样的变化，如果要填右括号，说明 \(k > dp(2n - i, t + 1)\)。
否则只能填左括号，可以发现只要能填，我们一定会填，不然就不够了，因为字典序的比较是比较前缀。
还可以发现，只要能填一定填，最后一定可以弄出合法的方案（走到 \(k = 1\)，最后一段全部填右括号）。
于是就以总复杂度 \(O(n^2)\) 的时间解决了这个问题。
POJ1037ψ(｀∇´)ψ
大概是问你字典序第 \(k\) 小的好排列个数。
好排列是指在值域上像波浪一样分布的数列。
数列长度不超过 \(20\) 所以你也可以看做是一个数。
这个很容易想到直接数位 dp，求方案，剩下的部分就考虑一下每一位能填什么就行了。
思路应该是类似的。