QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#50413 | #4842. Rectangle Placement | YaoBIG# | AC ✓ | 2ms | 3808kb | C++17 | 1.9kb | 2022-09-25 23:37:42 | 2022-09-25 23:37:44 |
Judging History
answer
#include "bits/stdc++.h"
#define rep(i, a, n) for (int i = a; i <= n; ++i)
#define revrep(i, a, n) for (int i = n; i >= a; --i)
using namespace std;
void debug_out() { cerr << endl; }
template<class H, class... T> void debug_out(H h, T... t) {
cerr << " " << to_string(h);
debug_out(t...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
using vi = vector<int>;
using ll = long long;
using pii = pair<int, int>;
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); }
};
const int mod = 998244353;
using Mint = Z<mod>;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m; cin >> n >> m;
auto binom = [](int n, int m) -> Mint {
Mint res = 1;
rep(i, 0, m - 1) res *= n - i;
rep(i, 1, m) res /= i;
return res;
};
auto separate = [&](int n) {
return binom(n, 4);
};
auto contain = [&](int n) {
return binom(n, 4);
};
auto tot = [&](int n) {
return binom(n, 2) * binom(n, 2);
};
Mint res = 0;
res += separate(n) * tot(m);
res += separate(m) * tot(n);
res -= separate(n) * separate(m) * 2;
res += contain(n) * contain(m);
printf("%d\n", (int) res);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3704kb
input:
4 5
output:
275
result:
ok 1 number(s): "275"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3596kb
input:
723435135 239873451
output:
832099301
result:
ok 1 number(s): "832099301"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
10348683 1000000000
output:
959472414
result:
ok 1 number(s): "959472414"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
1000000000 886687075
output:
994294391
result:
ok 1 number(s): "994294391"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3740kb
input:
238133469 977550485
output:
181382226
result:
ok 1 number(s): "181382226"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3748kb
input:
895943525 1000000000
output:
574248092
result:
ok 1 number(s): "574248092"
Test #7:
score: 0
Accepted
time: 2ms
memory: 3764kb
input:
1000000000 772281920
output:
2306050
result:
ok 1 number(s): "2306050"
Test #8:
score: 0
Accepted
time: 2ms
memory: 3660kb
input:
123728314 859786182
output:
722858859
result:
ok 1 number(s): "722858859"
Test #9:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
76505681 1000000000
output:
94904116
result:
ok 1 number(s): "94904116"
Test #10:
score: 0
Accepted
time: 2ms
memory: 3772kb
input:
1000000000 952844073
output:
632222340
result:
ok 1 number(s): "632222340"
Test #11:
score: 0
Accepted
time: 2ms
memory: 3724kb
input:
599257776 36989190
output:
592333335
result:
ok 1 number(s): "592333335"
Test #12:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
257067834 1000000000
output:
520152555
result:
ok 1 number(s): "520152555"
Test #13:
score: 0
Accepted
time: 2ms
memory: 3768kb
input:
1000000000 133406229
output:
769022397
result:
ok 1 number(s): "769022397"
Test #14:
score: 0
Accepted
time: 2ms
memory: 3760kb
input:
484852621 919224885
output:
829749309
result:
ok 1 number(s): "829749309"
Test #15:
score: 0
Accepted
time: 2ms
memory: 3648kb
input:
437629987 1000000000
output:
388969627
result:
ok 1 number(s): "388969627"
Test #16:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
1000000000 313968382
output:
471013029
result:
ok 1 number(s): "471013029"
Test #17:
score: 0
Accepted
time: 2ms
memory: 3596kb
input:
665414774 326352585
output:
424688776
result:
ok 1 number(s): "424688776"
Test #18:
score: 0
Accepted
time: 2ms
memory: 3736kb
input:
1000000000 1000000000
output:
656213933
result:
ok 1 number(s): "656213933"
Test #19:
score: 0
Accepted
time: 2ms
memory: 3668kb
input:
4 4
output:
71
result:
ok 1 number(s): "71"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
4 1000000000
output:
946327704
result:
ok 1 number(s): "946327704"
Test #21:
score: 0
Accepted
time: 2ms
memory: 3712kb
input:
1000000000 4
output:
946327704
result:
ok 1 number(s): "946327704"