QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#54637 | #977. Local Maxima | YaoBIG# | AC ✓ | 2733ms | 143888kb | C++ | 4.3kb | 2022-10-09 22:03:22 | 2022-10-09 22:03:24 |
Judging History
answer
#include "bits/stdc++.h"
#define rep(i, a, n) for (auto i = a; i <= (n); ++i)
#define revrep(i, a, n) for (auto i = n; i >= (a); --i)
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
template<class T> bool chmin(T &a, T b) { if (b < a) { a = b; return 1; } else return 0; }
template<class T> bool chmax(T &a, T b) { if (b > a) { a = b; return 1; } else return 0; }
using namespace std;
template<class A> string to_string(const A &v) {
bool first = 1;
string res = "{";
for (const auto &x: v) {
if (!first) res += ", ";
first = 0;
res += to_string(x);
}
res += ")";
return res;
}
void debug_out() { cerr << endl; }
template<class H, class... T> void debug_out(const H&h, const T&... t) {
cerr << " " << to_string(h);
debug_out(t...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<int>;
template<class T> struct Point {
using P = Point;
using type = T;
static constexpr T eps = 1e-9;
static constexpr bool isInt = is_integral_v<T>;
static int sgn(T x) { return (x > eps) - (x < -eps); }
static int cmp(T x, T y) { return sgn(x - y); }
T x, y;
P operator +(P a) const { return P{x + a.x, y + a.y}; }
P operator -(P a) const { return P{x - a.x, y - a.y}; }
P operator *(T a) const { return P{x * a, y * a}; }
P operator /(T a) const { return P{x / a, y / a}; }
bool operator ==(P a) { return cmp(x, a.x) == 0 && cmp(y, a.y) == 0; }
T len2() const { return x * x + y * y; }
T len() const { return sqrt(x * x + y * y); }
P unit() const {
if (isInt) return *this;
else return len() <= eps ? P{} : *this / len();
}
T dot(P b) const { return x * b.x + y * b.y; }
T cross(P b) const { return x * b.y - y * b.x; }
P rotate(T theta) const {
P a{cos(theta), sin(theta)};
return P{x * a.x - y * a.y, x * a.y + y * a.x};
}
T project_len(P a, P b) const {
if (isInt) return (*this - a).dot(b - a);
else if (a == b) return 0;
else return (*this - a).dot(b - a) / (b - a).len();
}
T dis_to_line(P a, P b) const {
if (isInt) return (*this - a).cross(b - a);
else if (a == b) return 0;
else return (*this - a).cross(b - a) / (b - a).len();
}
T dis_to_seg(P a, P b) const {
if (project_len(a, b) <= eps) return (*this - a).len();
if (project_len(b, a) <= eps) return (*this - b).len();
return fabs(dis_to_line(a, b));
}
friend string to_string(P p) { return "(" + to_string(p.x) + ", " + to_string(p.y) + ")"; }
};
template<const int &mod> struct Z {
int x;
Z(ll a = 0): x (a % mod) { if (x < 0) x += mod; }
explicit operator int() const { return x; }
Z& operator +=(Z b) { x += b.x; if (x >= mod) x -= mod; return *this; }
Z& operator -=(Z b) { x -= b.x; if (x < 0) x += mod; return *this; }
Z& operator *=(Z b) { x = 1ll * x * b.x % mod; return *this; }
friend Z operator +(Z a, Z b) { return a += b; }
friend Z operator -(Z a, Z b) { return a -= b; }
friend Z operator *(Z a, Z b) { return a *= b; }
Z pow(ll k) const {
Z res = 1, a = *this;
for (; k; k >>= 1, a = a * a) if (k & 1) res = res * a;
return res;
}
Z& operator /=(Z b) {
assert(b.x != 0);
*this = *this * b.pow(mod - 2);
return *this;
}
friend Z operator /(Z a, Z b) { return a /= b; }
friend string to_string(Z a) { return to_string(a.x); }
};
int mod;
using Mint = Z<mod>;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m; cin >> n >> m >> mod;
vector<Mint> fac(n * m + 1), inv(n * m + 1), ifac(n * m + 1);
fac[0] = inv[1] = ifac[0] = 1;
rep(i, 2, n * m) inv[i] = inv[mod % i] * (mod - mod / i);
rep(i, 1, n * m) fac[i] = fac[i - 1] * i;
rep(i, 1, n * m) ifac[i] = ifac[i - 1] * inv[i];
auto binom = [&](int n, int m) -> Mint {
if (m < 0 || n < m) return 0;
else return fac[n] * ifac[m] * ifac[n - m];
};
vector<vector<Mint>> dp(n + 1, vector<Mint>(m + 1));
dp[1][1] = n * m;
rep(i, 1, n) rep(j, 1, m) {
if (i < n) {
dp[i + 1][j] += dp[i][j] * (n - i) * j * binom(j - 1 + n * m - (i + 1) * j, j - 1) * fac[j - 1];
}
if (j < m) {
dp[i][j + 1] += dp[i][j] * (m - j) * i * binom(i - 1 + n * m - (j + 1) * i, i - 1) * fac[i - 1];
}
}
printf("%d\n", (int) dp[n][m]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3692kb
input:
2 2 1000000007
output:
16
result:
ok "16"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
4 3 1000000007
output:
95800320
result:
ok "95800320"
Test #3:
score: 0
Accepted
time: 5ms
memory: 3956kb
input:
100 100 998244353
output:
848530760
result:
ok "848530760"
Test #4:
score: 0
Accepted
time: 4ms
memory: 3880kb
input:
79 78 435515903
output:
306910591
result:
ok "306910591"
Test #5:
score: 0
Accepted
time: 3ms
memory: 3780kb
input:
69 74 715090997
output:
611101520
result:
ok "611101520"
Test #6:
score: 0
Accepted
time: 4ms
memory: 3752kb
input:
77 67 221878187
output:
215381310
result:
ok "215381310"
Test #7:
score: 0
Accepted
time: 3ms
memory: 3852kb
input:
70 66 537039721
output:
352526401
result:
ok "352526401"
Test #8:
score: 0
Accepted
time: 2119ms
memory: 114172kb
input:
2952 2408 973899449
output:
400429421
result:
ok "400429421"
Test #9:
score: 0
Accepted
time: 1727ms
memory: 97948kb
input:
2484 2435 713449813
output:
79762013
result:
ok "79762013"
Test #10:
score: 0
Accepted
time: 2456ms
memory: 129676kb
input:
2904 2783 227396761
output:
120446329
result:
ok "120446329"
Test #11:
score: 0
Accepted
time: 2270ms
memory: 123896kb
input:
2654 2908 161249083
output:
100452853
result:
ok "100452853"
Test #12:
score: 0
Accepted
time: 2257ms
memory: 120452kb
input:
2819 2657 722796007
output:
643358934
result:
ok "643358934"
Test #13:
score: 0
Accepted
time: 2733ms
memory: 143888kb
input:
3000 3000 143115311
output:
76718331
result:
ok "76718331"