Submission #259299

#TimeUsernameProblemLanguageResultExecution timeMemory
259299BruteforcemanRuins 3 (JOI20_ruins3)C++11
58 / 100
6024 ms13176 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 605; 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 * 2][maxn * 2]; 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; } long long dp[maxn][maxn]; int main() { int n; 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; i++) { memset(mem, -1, sizeof mem); var = i; ways[i] = calc(var, 0); } memset(mem, -1, sizeof mem); dp[n][0] = 1; for(int cur = n - 1; cur >= 0; cur--) { for(int bound = 0; bound <= n; bound++) { dp[cur][bound] = (1LL * 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) { long long add = ((C[free][bound - i] * ways[bound - i] % mod) * dp[cur + 1][i]) % mod; dp[cur][bound] += add; dp[cur][bound] %= mod; } } } } cout << dp[0][n] << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...