이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll mod = 1000000007;
const int maxn = 3000 + 1;
ll dp[maxn][maxn];
bool ready[maxn][maxn];
ll sum(ll x) {
return ((x * (x-1)) / 2) % mod;
}
ll solve(ll h, ll w) {
if (h < 0 || w < 0)
return 0;
if (h == 0 || w == 0)
return 1;
if (ready[h][w])
return dp[h][w];
ll ans = 0;
// place nothing
ans = solve(h-1, w);
// place 1
ans += (solve(h-1, w-1) * w * 4) % mod;
ans %= mod;
// place 2 in same row
ans += (solve(h-1, w-2) * sum(w)) % mod;
ans %= mod;
// place 2 in same column
ans += (solve(h-2, w-1) * (h-1) * w) % mod;
ans %= mod;
ready[h][w] = true;
dp[h][w] = ans;
return ans;
}
int main() {
int h, w;
cin >> h >> w;
cout << (solve(h, w) - 1 + mod) % mod << '\n';
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |