#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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
600 KB |
Output is correct |
| 7 |
Correct |
0 ms |
604 KB |
Output is correct |
| 8 |
Correct |
1 ms |
604 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
2 ms |
804 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
2 ms |
1116 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
600 KB |
Output is correct |
| 7 |
Correct |
0 ms |
604 KB |
Output is correct |
| 8 |
Correct |
1 ms |
604 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
2 ms |
804 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
860 KB |
Output is correct |
| 15 |
Correct |
158 ms |
45456 KB |
Output is correct |
| 16 |
Correct |
3 ms |
3164 KB |
Output is correct |
| 17 |
Correct |
15 ms |
10328 KB |
Output is correct |
| 18 |
Correct |
33 ms |
12964 KB |
Output is correct |
| 19 |
Correct |
155 ms |
52792 KB |
Output is correct |
| 20 |
Correct |
117 ms |
42348 KB |
Output is correct |
| 21 |
Correct |
73 ms |
27996 KB |
Output is correct |
| 22 |
Correct |
74 ms |
27740 KB |
Output is correct |
| 23 |
Correct |
45 ms |
15704 KB |
Output is correct |
| 24 |
Correct |
234 ms |
72588 KB |
Output is correct |
| 25 |
Correct |
154 ms |
53848 KB |
Output is correct |
| 26 |
Correct |
170 ms |
61788 KB |
Output is correct |
| 27 |
Correct |
189 ms |
69716 KB |
Output is correct |
