给定一个序列，当序列不是单调上升（非严格，之后的"单调上升"也同样是非严格）时，删去一个数
一直删到序列单调上升，问你有多少种操作方案
设 \(F_k\) 为删第 \(k\) 个数时序列刚好单调上升（之前都没有）的方案数
答案显然等于 \(\sum_{i = 1}^{n} F_i\)
直接求 \(F_k\) 有太多限制条件了，考虑用容斥原理
先求出 \(g_k\) 为删掉 \(k\) 个数可以使得序列单调上升的方案数
但直接这个求也不是很好求，考虑换一种方式求它
我们可以用树状数组 \(O(n^2logn)\) 求出长度为 \(k\) 的单调上升子序列的个数 \(f _ k\)
\(g_k = k! \times f_{n-k}\)
显然在删了 \(k\) 个数之后序列单调上升了的话，在此基础上删 \(1,2,3\cdots\) 个也可以使得序列单调上升
所以
\[
F_k = g_k - \sum_{i = 0} ^ {k - 1} perm(n - i, k - i) \times F_i \perm(n,k) 表示n个数里选k个数的排列的方案数
\]
特别的，\(F_0 = g_0\)
原文：https://www.cnblogs.com/Lskkkno1/p/11424209.html