1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
| #include <bits/stdc++.h> #define FOR(i, x, y) for (remove_const<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i) #define FORD(i, x, y) for (remove_const<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i) using namespace std; typedef long long LL; const int maxn = 1200 + 5; const int MOD = 1E9 + 7; LL dp[maxn][maxn], n, a[maxn], l[maxn]; LL invf[maxn], factor[maxn];
LL quick_inverse(LL n, LL p) { LL ret = 1; LL exponent = p - 2; for (LL i = exponent; i; i >>= 1, n = n * n % p) { if (i & 1) { ret = ret * n % p; } } return ret; }
void get_factorial_inverse(LL n, LL p) { factor[0] = 1; for (LL i = 1; i <= n; ++i) { factor[i] = i * factor[i - 1] % p; } invf[n] = quick_inverse(factor[n], p); for (LL i = n-1; i >= 0; --i) { invf[i] = invf[i + 1] * (i + 1) % p; } }
inline LL A(LL n, LL m) { return factor[n] * invf[n - m] % MOD; }
int main() { cin >> n; get_factorial_inverse(n, MOD); FOR(i, 0, n) scanf("%lld", &a[i]); l[0] = 1; FOR(i, 1, n) if (a[i] >= a[i - 1]) l[i] = l[i - 1] + 1; else l[i] = 1; FOR(i, 1, n + 1) { FOR(j, 1, l[i - 1] + 1) { if (i == l[i - 1]) dp[i][i] = 1; FOR(k, j, i - j + 1) dp[i][j] = (dp[i][j] + dp[i - j][k] * A(k, j)) % MOD; } } LL ans = 0; FOR(i, 1, l[n - 1] + 1) ans += dp[n][i]; cout << ans % MOD << endl; }
|