妙啊！
首先有两个显然的结论：
Ln=n。
[i−Li+1,i] 之间只会互相包含或不交，不会部分相交。
不满足上述两者直接输出 0。
于是不难发现 [i−Li+1,i] 之间的包含关系形成了一个树形结构，根为 [1,n]。
设 F(i) 表示对于连续区间 [i−Li+1,i] 内的 L，安排这一区间内的大小关系的合法方案数（可以视为一个 Li 阶排列）。
则答案即 F(n)。
设 f(k) 表示满足 Li=1 (1≤i≤k) 的 k+1 阶排列个数。
设 [i−Li+1,i] 在树上有 k 个儿子 c1,c2,…,ck，则有 F(n)=f(k)k∏i=1F(ci)
因为这些儿子分别也是极长连续区间，所以若其中的安排顺序使得这些儿子之间按照大小关系形成了连续区间，则这样的连续区间会导致儿子不满足极长，所以儿子之间的顺序应当是 f(k) 种方案。
设 si 表示 [i−Li+1,i] 的儿子个数，则由上式不难得出答案即 n∏i=1f(si)
si 可以通过单调栈求出。
那么只需要考虑预处理求出 f 即可。
给出一个结论：f(k) 等价于每个长度大于 1 的连续区间都包含最大值的 k+1 阶排列个数。
证明可以考虑将 f 的原定义中的排列取逆，则连续区间的位置与值域将交换。
考虑推导 f 的递推式。
不同地，从 k−1 到 k，考虑将所有数加一并插入一个新的 1。
分类讨论：
若插入前原排列合法，则 1 只有插入在 2 旁边时才可能形成一个新的长度大于 1 的不包含最大值的连续区间。
此部分方案数为 (k−1)f(k−1)。若插入前原排列不合法，则最多只会有一个不包含最大值的极长连续区间。因为插入 1 无法同时破坏两个极长连续区间。 枚举这个区间的长度为 i，设其在原排列中值域为 [x,x+i−1]，则易知 x≥2,x+i−1<k，从而 2≤x≤k−i。
则这个区间内的元素顺序和 1 插入的位置可以看做一个 i+1 阶排列，即把 1 看做这个排列中的 i+1，而删去这个 i+1 可以删去所有连续区间，故方案数为 f(i)。
另外，考虑这个连续区间的位置，不难得到安排这个连续区间与其他元素的相对位置的方案数为 f(k−i)。
综上， f(k)=(k−1)f(k−1)+k−2∑i=2(k−i−1)f(i)f(k−i)=(k−1)f(k−1)+k−2∑i=2(i−1)f(i)f(k−i)(k≥2)
分治 NTT 即可。
学习某大佬写左闭右开或许会好写亿点？
（明明就是自己不会写就抄了别人的代码吧）
代码：
1 |
|