Description

给出一个长度为 \(n\) 的序列 \(A\) 。如果序列 \(A\) 不是非降的，你必须从中删去一个数，这一操作，直到 \(A\) 非降为止。求有多少种不同的操作方案，答案模 \(10^9+7\) 。

\(1\leq n\leq 2000\)

Solution

显然对于 \(A\) 的一个长度为 \(l\) 的单调不降子序列 \(B\) 。删数而得到它的方案数为 \((n-l)!\) 。

但是这样会有不合法的情况，即长度为 \(l+1\) 的单调不降子序列被删。

记长度为 \(l\) 的单调不降子序列个数为 \(f_l\) ，那么答案为：

\[\sum_{l=1}^{n-1} f_l\cdot(n-l)!-f_{l+1}\cdot(n-l-1)!\cdot(i+1)\]

那么剩下的就是求单调不降子序列的个数了。可以用树状数组来优化这个过程，复杂度为 \(O(n^2log_2n)\) ，为整个算法的瓶颈。

Code

//It is made by Awson on 2018.3.26#include 
    
     #define lowbit(x) ((x)&(-(x)))using namespace std;const int N = 2000, yzh = 1e9+7; int n, a[N+5], fac[N+5], b[N+5], f[N+5];struct bittree {    int c[N+5];    void add(int x, int val) {while (x <= n) (c[x] += val) %= yzh, x += lowbit(x); }    int count(int x) {int ans = 0; while (x) (ans += c[x]) %= yzh, x -= lowbit(x); return ans; }}T[N+5]; void work() {    scanf("%d", &n);    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];    fac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = 1ll*i*fac[i-1]%yzh;    sort(b+1, b+n+1);    for (int i = 1; i <= n; i++) a[i] = lower_bound(b+1, b+n+1, a[i])-b;    T[0].add(1, 1);    for (int i = 1; i <= n; i++)    for (int l = i; l >= 1; l--) {        int t = T[l-1].count(a[i]); (f[l] += t) %= yzh;        T[l].add(a[i], t);    }    int ans = 0;    for (int i = 1; i < n; i++) {    (ans += 1ll*f[i]*fac[n-i]%yzh) %= yzh;    (ans -= 1ll*f[i+1]*fac[n-i-1]%yzh*(i+1)%yzh) %= yzh;    }    printf("%d\n", (ans+yzh)%yzh);}int main() {work(); return 0; }