14193: 【原4193】isn

题目

题目描述

author: Sakiko 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4193

Description

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

Input Format

第一行一个整数 \(T\) , 代表数据组数。
对于每组数据，第一行一个整数 \(n\) 。
接下来一行 \(n\) 个整数，描述 \(A\) 。

Output Format

\(T\) 行，每行一个整数，描述答案。

Sample Input

1
4
1 7 5 3

Sample Output

18

Data Range

对于10%的数据，\(1<=n<=10\)。
对于30%的数据，\(1<=n<=20\)。
对于50%的数据，\(1<=n<=50\)。
对于70%的数据，\(1<=n<=200\)。
对于100%的数据，\(1<=n<=2000, T<=5\)。

zqy2018's solution

/*
    See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu4193.md
*/
#include <bits/stdc++.h>
#define INF 2000000000
#define M 1000000007
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int fac[2005];
int n, a[2005];
int f[2005][2005], tot;
int c[2005], l[2005];
pair<int, int> b[2005];
inline int lowbit(int x){
    return x & (-x);
}
inline int modadd(int x, int y){
    return (x + y >= M ? x + y - M: x + y);
}
void add(int r, int x){
    while (r <= n)
        c[r] = modadd(c[r], x), r += lowbit(r);
}
int query(int r){
    int res = 0;
    while (r > 0)
        res = modadd(res, c[r]), r -= lowbit(r);
    return res;
}
void init(){
    n = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read(), b[i] = make_pair(a[i], i);
    sort(b + 1, b + n + 1);
}
void solve(){
    memset(f, 0, sizeof(f));
    memset(l, 0, sizeof(l));
    l[1] = n;
    for (int i = 1; i <= n; ++i)
        f[i][1] = 1;
    for (int j = 2; j <= n; ++j){
        for (int i = 0; i <= n; ++i)
            c[i] = 0;
        for (int i = 1; i <= n; ++i){
            int pos = b[i].second;
            f[pos][j] = query(pos - 1);
            add(pos, f[pos][j - 1]);
        }
        for (int i = j; i <= n; ++i)
            l[j] = modadd(l[j], f[i][j]);
    }
    int ans = l[n];
    for (int i = n - 1; i >= 1; --i){
        int t = 1ll * l[i] * fac[n - i] % M;
        t = modadd(t, M - 1ll * (1ll * l[i + 1] * fac[n - i - 1] % M) * (i + 1) % M);
        ans = modadd(ans, t);
    }
    printf("%d\n", ans);
}
int main(){
    int T = read();
    fac[0] = fac[1] = 1;
    for (int i = 2; i <= 2000; ++i)
        fac[i] = 1ll * fac[i - 1] * i % M;
    while (T--){
        init();
        solve();
    }
    return 0;
}