Submission #45797216

---

Source Code Expand

// LUOGU_RID: 125601756
#include <bits/stdc++.h>
#define debug cerr << "[" << __LINE__ << "] "
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> inline void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> inline void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> inline void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	x *= f;
}
const int N = 2010, MOD = 1e9 + 7;
int n, a[N], f[N][N];
inline void add(int &x, ll y) { x = (x + y) % MOD; }
struct BIT {
	int t[N];
	void Add(int x, int y) {
		x++;
		for (; x <= n + 2; x += x & -x) add(t[x], y);
	}
	int query(int x) {
		x++;
		int s = 0;
		for (; x; x -= x & -x) add(s, t[x]);
		return s;
	}
	int query(int l, int r) {
		return (query(r) - query(l - 1) + MOD) % MOD;
	}
} A[N], b[N], c[N];
int inv[N];
inline void binom(int x) {
	inv[1] = 1;
	F(i, 2, x) inv[i] = (ll) (MOD - MOD / i) * inv[MOD % i] % MOD;
}
signed main() {
	read(n);
	binom(n);
	F(i, 1, n) read(a[i]);
	F(i, 0, n + 1)
		F(j, 0, i)
			A[j].Add(a[i], 1);
	a[n + 1] = n + 1;
	F(len, 3, n + 2)
		for (int i = 0, j = len - 1; j <= n + 1; i++, j++) {
			if (a[i] > a[j]) continue;
			int g = A[i + 1].query(a[i], a[j]) - A[j].query(a[i], a[j]);
			if (g) f[i][j] = ((ll) (b[i].query(a[i], a[j]) + c[j].query(a[i], a[j])) * inv[g] + 1) % MOD;
			// debug << i << " " << j << " " << f[i][j] << " " << g << endl;
			b[i].Add(a[j], f[i][j]);
			c[j].Add(a[i], f[i][j]);
		}
	cout << f[0][n + 1];
	return 0;
}

Submission Info

Judge Result