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;
using ll = long long;
const int MOD = 1e9+7;
vector<vector<bool>> ready;
vector<vector<ll>> dp;
// there are h rows and w columns left
ll solve(int h, int 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);
ans %= MOD;
// place one tent in this row
// this eliminates one row, one column, and there are 4 different directions the opening can be
ans += 4*solve(h-1, w-1)*w;
ans %= MOD;
// place two tents in this row
// this eliminates one row, two columns and you can place the two tents in w choose 2 different ways
ans += solve(h-1, w-2)*(w*(w-1)/2);
ans %= MOD;
// place two tents in one column, but one of them is in this row
// this eliminates two rows, one column and you can choose the column w ways and choose the other row (h-1) ways
ans += solve(h-2, w-1)*w*(h-1);
ans %= MOD;
ready[h][w] = true;
return dp[h][w] = ans;
}
int main() {
int h, w;
cin >> h >> w;
ready.resize(h+1, vector<bool>(w+1));
dp.resize(h+1, vector<ll>(w+1));
cout << (solve(h, w)+MOD-1) % MOD << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |