This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 605 * 2;
const long long mod = 1e9 + 7;
long long ways[maxn];
int a[maxn];
long long binpow(long long x, long long y) {
long long ans = 1;
long long power = x;
while(y) {
if(y & 1) ans = (ans * power) % mod;
power = (power * power) % mod;
y >>= 1;
}
return ans;
}
long long inv(long long x) {
return binpow(x % mod, mod - 2);
}
int var;
long long mem[maxn][maxn];
long long C[maxn][maxn];
long long fac[] = {1, 1, 2};
long long calc(int cur, int take) {
long long ans = 0;
if(cur == 1) {
for(int i = 0; i <= 2; i++) {
if(take + i == var + 1) {
return (C[take + i][i] * inv(fac[2 - i])) % mod;
}
}
return 0;
}
if(mem[cur][take] != -1) return mem[cur][take];
for(int i = 0; i <= 2; i++) {
if(take + i <= var - cur + 1) {
long long add = (calc(cur - 1, take + i) * C[take + i][i]) % mod;
ans += (add * inv(fac[2 - i])) % mod;
ans %= mod;
}
}
return mem[cur][take] = ans;
}
int n;
long long fn[maxn][maxn];
long long dp(int cur, int bound) {
if(cur == n) return (bound == 0);
if(fn[cur][bound] != -1) return fn[cur][bound];
long long ans = (dp(cur + 1, bound) * (n - bound - cur)) % mod;
for(int i = 0; i < bound; i++) {
int free = a[cur + 1] - (n - bound + (cur + 1));
if(free < bound - i) continue;
ans += ((C[free][bound - i] *
ways[bound - i]) % mod) * dp(cur + 1, i);
ans %= mod;
}
return fn[cur][bound] = ans;
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 0; i <= n + n; i++) {
C[i][0] = 1;
for(int j = 1; j <= i; j++) {
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
}
for(int i = 1; i <= n + n; i++) {
memset(mem, -1, sizeof mem);
var = i;
ways[i] = calc(var, 0);
}
memset(fn, -1, sizeof fn);
cout << ((a[n] != n + n) ? 0 : dp(0, n)) << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |