QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#54637#977. Local MaximaYaoBIG#AC ✓2733ms143888kbC++4.3kb2022-10-09 22:03:222022-10-09 22:03:24

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-09 22:03:24]
  • 评测
  • 测评结果:AC
  • 用时:2733ms
  • 内存:143888kb
  • [2022-10-09 22:03:22]
  • 提交

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"