「loj - 2554」青蕈领主

link。


首先如果 \(L_n \neq n\) 则无解,以下默认 \(L_n = n\)。


记 \(l_i = i - L_i + 1\),即最长连续段的左端点。

由一些基本常识,连续段的交、并、差仍是连续段;这可以推出所有 \([l_i, i]\) 互相包含或相离(如果不满足,则无解)。

建出树形结构:根为 \([1, n]\);对于 \([l_i, i]\),如果 \(l_i = i\) 则它为叶子;否则它的儿子为 \([l_{i - 1}, i - 1];[l_{l_{i - 1} - 1}, l_{i - 1} - 1];\dots\)。

不难发现 \([l_i, i]\) 子树内怎么定方案与外部无关,那么只需要考虑每个点的所有儿子如何分配方案,将所有点的贡献相乘即可。

也即,如果记 \(f_i\) 表示有 \(i\) 个儿子的方案数,记 \(deg_i\) 表示 \(i\) 的儿子个数,则答案为 \(\prod_{i = 1}^{n}f_{deg_i}\)。


然后我们进入 counting 环节。

先考虑 \(f_n\) 的一个等价定义:长度为 \(n + 1\) 的排列,其中 \(L_{1\dots n} = 1, L_{n + 1} = n + 1\) 的方案数。

比较难看出 \(\{f_n\}\) 可能具有的递归结构,那么正难则反。

总方案数为 \((n + 1)!\),其中不合法当且仅当根 \([1, n + 1]\)的儿子个数 \(< n\)。

注意我们只考虑了根,根以下的子树没有加以任何限制,所以贡献为子树大小的阶乘。

因此,如果记 \(G(x) = \sum_{n > 0} n!x^n\),则有 \(f_n = (n + 1)! - \sum_{i = 1}^{n - 1} f_i[x^n]G^{i}(x)\)。


以下依然记 \(G(x) = \sum_{n > 0} n!x^n\)。

事实上,如果记 \(F(x) = \sum_{n \geq 0} f_nx^n\),则有一个组合意义更明显的式子:

\[F(G(x)) = \sum_{n\geq 0}(n + 1)!x^n \]

即依据根的儿子个数,将所有 \((n + 1)!\) 种排列分类。

将右边也化成 \(G(x)\) 的形式,得到:\(xF(G(x)) = G(x)\)。

如果记 \(H(x)\) 是 \(G(x)\) 的复合逆,则:\(F(x) = x / H(x)\)。

太好了,套用复合逆算法卡卡常说不定就过了。


注意到 \(G\) 是经典的微分有限。事实上,根据 \(g_n = ng_{n - 1}\),有 \(G = x^2G' + xG\)。

将 \(x\) 代换成 \(H(x)\):

\[\begin{aligned} G(x) &= x^2\frac{dG(x)}{dx} + xG(x) \\ x &= H^2\frac{dG(H)}{dH} + Hx \\ x &= H^2\frac{dx}{dH} + Hx \\ x &= (x/F)^2(\frac{1}{(x/F)'}) + (x/F)x \\ 0 &= F^2 - xF'F - 2xF + x^2F' + xF' - F \end{aligned} \]

我承认,最后一步跳得有点快。

取第 \(n\) 项,得到 \(0 = \sum_{i = 0}^{n}f_if_{n - i} - \sum_{i = 0}^{n}i\times f_if_{n - i} - 2f_{n - 1} + (n - 1)f_{n - 1} + nf_n - f_n\)。

那么有递推式 \(f_n = \sum_{i = 1}^{n - 1}(i - 1)\times f_if_{n - i} - (n - 3)f_{n - 1}\)。

或者说 \(f_n = \sum_{i = 2}^{n - 2}(i - 1)\times f_if_{n - i} + (n - 1)f_{n - 1}\)。

条件 \(f_0 = 1\)。

之后再做个分治 fft 即可,复杂度 \(O(n\log^2 n)\)。


另一种推导方法:https://blog.csdn.net/qq_39972971/article/details/89408417

最后依然是求助环节:有没有懂哥愿意教教我 simple permutations 咋数啊。

上一篇:ResponseBodyAdvice处理返回数据


下一篇:去除win8.1这台电脑中的6个库文件夹