이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll; typedef pair<int, int> pii;
#define pb emplace_back
#define AI(x) begin(x),end(x)
#define ff first
#define ss second
#ifdef OWO
#define debug(args...) LKJ("\033[0;32m[ " + string(#args) + " ]\033[0m", args)
template <class I> void LKJ(I&&x) { cerr << x << endl; }
template <class I, class...T> void LKJ(I&&x, T&&...t) { cerr << x << ", "; LKJ(t...); }
template <class I> void OI(I a, I b) { while (a < b) cerr << *a << " \n"[next(a) == b]; }
#else
#define debug(...) 0
#define OI(...) 0
#endif
const int MOD = 1'000'000'007;
int mad(int u, int v) {
u += v - MOD;
u += MOD & (u >> 31);
return u;
}
int mul(int u, int v) {
return (ll) u * v % MOD;
}
int mow(int x, int e) {
int r = 1;
while (e) {
if (e & 1) r = mul(r, x);
x = mul(x, x);
e >>= 1;
}
return r;
}
const int kN = 3003;
int fac[kN], caf[kN], inv[kN];
void init(int n) {
fac[0] = 1;
for (int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i);
caf[n] = mow(fac[n], MOD - 2);
for (int i = n; i >= 1; --i) caf[i - 1] = mul(caf[i], i);
for (int i = 1; i <= n; ++i) inv[i] = mul(fac[i - 1], caf[i]);
}
int C(int n, int k) {
if (0 > k or k > n) return 0;
return mul(fac[n], mul(caf[k], caf[n - k]));
}
int P(int n, int k) {
if (0 > k or k > n) return 0;
return mul(fac[n], caf[n - k]);
}
int H, W, ans;
int tmp[kN][kN];
int solve(int n, int m) {
if (n > m) swap(n, m);
if (tmp[n][m] != -1) return tmp[n][m];
tmp[n][m] = 0;
for (int i = 0; i <= n; ++i)
tmp[n][m] = mad(tmp[n][m], mul(mul(C(n, i), P(m, i)), mow(4, i)));
return tmp[n][m];
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> H >> W;
if (H > W) swap(H, W);
init(max(H, W));
for (int i = 0; i <= H; ++i)
for (int j = 0; j <= W; ++j)
tmp[i][j] = -1;
for (int r = 0; r <= H and 2 * r <= W; ++r)
for (int c = 0; r + 2 * c <= H and 2 * r + c <= W; ++c) {
int v = mul(C(H, r), mul(P(W, 2 * r), mow(inv[2], r)));
v = mul(v, mul(C(W - 2 * r, c), mul(P(H - r, 2 * c), mow(inv[2], c))));
v = mul(v, solve(H - (r + 2 * c), W - (2 * r + c)));
ans = mad(ans, v);
}
cout << mad(ans, MOD - 1) << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |