# 14193: 【原4193】isn

### 题目描述

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

## Output Format

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

## Sample Input

``````1
4
1 7 5 3
``````

## Sample Output

``````18
``````

## 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 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);
}
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(){
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);
}
for (int i = j; i <= n; ++i)
}
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);
}
printf("%d\n", ans);
}
int main(){