（容易观察得到，本文的公式都是直接从题解里面抄过来的。）
代码咕了，所以不从题解里面抄过来的内容全部不保证正确。
观察样例，发现对于 \(1\le n\le 3\) ，合法序列个数恰好是 \(n!\) ，所以猜想合法序列能和排列一一对应。
我的想法：
对于一个合法序列，从最大值的最左边出现位置 \(x\) 开始跳。如果 \(x\) 不是 \(a_x\) 的最右边出现位置那么往下一个位置跳（往右），否则往 \(a_x-1\) 的左端点跳（往左）。特别地， 1 的右端点往 \(mx\) 的左端点跳（任意）。这样可以构造出一个环，我们令起始点是 \(mx\) 的左端点，即可得到方案数 \(n!\) 。
从一个环+一个起始点对应回去也是类似的。
环+点怎么变成排列呢？那就是任取一个排列，连边 \(p_i\to p_{i+1}\) ，并令 \(p_1\) 是起始点即可。
现在就很好看了。对于一个排列，从 \(p_1\) 开始，分成若干个极长连续上升子段，那么每一段都是相同的，并且段之间单调递减。
由于这东西是很对称的，所以为了与题解统一，变成：分成若干个极长连续下降子段，每个位置对应的值是前面的小于号的个数。
对于一个值的出现次数，容易想到要考虑每个位置的贡献，所以要求出所有 \(f_{i,j}\) 表示 \(i\) 个数中恰好有 \(j\) 个小于号的方案数。
显然可以容斥。设 \(g_{i,j}\) 表示 \(i\) 个数“至少”有 \(j\) 个小于号的方案数（钦定 \(j\) 个小于号，其他随便摆），有 \(g_{i,j}=S(i,i-j)\times (i-j)!=i^{i-j}\) 。然后有 \(f_{i,j}=\sum_k {k\choose j}(-1)^{k-j}g_{i,k}\) 。
注意这里如果选择钦定 \(i-j-1\) 个大于号，那么容斥系数会变成 \({i-j-1 \choose i-k-1}(-1)^{i-k-1}\) ，会非常丑陋，甚至会使得下面推不出一个好看的形式。
此时我们有
注意到最后一个求和符与 \(k\) 无关，所以只要能预处理出后面，就可以在 \(O(n^2)\) 或 \(O(n\log n)\) 的时间内得到答案。暴力预处理也是 \(O(n^2)\) 的。
设 \(F={e^z-1\over z}\) ，再化简成
前者可以直接求出来，所以真正要求的就是 \([z^j]{F^{n-j+1}\over 1-F}\) 。这东西恰好是
设 \(w(z)=zF(z)\) ， \(\phi(z)\) 满足 \({w(z)\over \phi(w(z))}=z\) （即 \(\phi(z)={z\over w^{-1}}\) ），即 \({zF(z)\over \phi(w(z))}=z\) ，即 \(F(z)=\phi(w)\) 。
所以现在要求
（为什么要引入 \(\phi\) 呢？这样可以使得所有 \(z\) 外面都包着一个 \(w\) ，方便反演。）
反演，把 \(w\) 搞掉，得到
其中求导是对 \(z\) 求偏导。
暴力把求导展开，得到
现在把 \({u\over (1-uz)^2}\) 和 \({1\over 1-uz}\) 拆掉，经过推导得到
我们知道 \(w=e^z-1\) ，所以 \(\phi(z)={z\over \ln(z+1)}\) ，然后就只需要抄板子了。
两种容斥方法，竟然无法推到同一个结果（或者是推导的难度不太一样），非常离谱。
恒等式：
CF1349F Slime and Sequences [生成函数]
原文：https://www.cnblogs.com/p-b-p-b/p/14262895.html