QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#79538 | #4841. Geometry | hos_lyric | AC ✓ | 151ms | 121004kb | C++14 | 5.8kb | 2023-02-20 11:54:01 | 2023-02-20 11:54:02 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
static constexpr unsigned M = M_;
unsigned x;
constexpr ModInt() : x(0U) {}
constexpr ModInt(unsigned x_) : x(x_ % M) {}
constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
ModInt pow(long long e) const {
if (e < 0) return inv().pow(-e);
ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
}
ModInt inv() const {
unsigned a = M, b = x; int y = 0, z = 1;
for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
assert(a == 1U); return ModInt(y);
}
ModInt operator+() const { return *this; }
ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
explicit operator bool() const { return x; }
bool operator==(const ModInt &a) const { return (x == a.x); }
bool operator!=(const ModInt &a) const { return (x != a.x); }
friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////
constexpr unsigned MO = 998244353;
using Mint = ModInt<MO>;
constexpr int LIM_INV = 6'000'010;
Mint inv[LIM_INV], fac[LIM_INV], invFac[LIM_INV];
void prepare() {
inv[1] = 1;
for (int i = 2; i < LIM_INV; ++i) {
inv[i] = -((Mint::M / i) * inv[Mint::M % i]);
}
fac[0] = invFac[0] = 1;
for (int i = 1; i < LIM_INV; ++i) {
fac[i] = fac[i - 1] * i;
invFac[i] = invFac[i - 1] * inv[i];
}
}
Mint binom(Int n, Int k) {
if (n < 0) {
if (k >= 0) {
return ((k & 1) ? -1 : +1) * binom(-n + k - 1, k);
} else if (n - k >= 0) {
return (((n - k) & 1) ? -1 : +1) * binom(-k - 1, n - k);
} else {
return 0;
}
} else {
if (0 <= k && k <= n) {
assert(n < LIM_INV);
return fac[n] * invFac[k] * invFac[n - k];
} else {
return 0;
}
}
}
Mint prodFac[LIM_INV + 1], prodInvFac[LIM_INV + 1];
void prepareProdFac() {
prodFac[0] = prodInvFac[0] = 1;
for (int i = 0; i < LIM_INV; ++i) {
prodFac[i + 1] = prodFac[i] * fac[i];
prodInvFac[i + 1] = prodInvFac[i] * invFac[i];
}
}
// \prod_{i=0}^{l-1} \prod_{j=0}^{m-1} \prod_{k=0}^{n-1} (i+j+k+2)/(i+j+k+1)
Mint planePartition(int l, int m, int n) {
assert(l >= 0); assert(m >= 0); assert(n >= 0);
return prodFac[l + m + n] * prodInvFac[m + n] * prodInvFac[n + l] * prodInvFac[l + m] * prodFac[l] * prodFac[m] * prodFac[n];
}
int main() {
prepare();
prepareProdFac();
for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
int A[3];
for (int i = 0; i < 3; ++i) {
scanf("%d", &A[i]);
}
sort(A, A + 3);
chmin(A[2], A[0] + A[1]);
Int bs[3];
for (int i = 0; i < 3; ++i) {
bs[i] = A[(i + 1) % 3] + A[(i + 2) % 3] - A[i];
}
// cerr<<"bs = ";pv(bs,bs+3);
Int area = (bs[0] + bs[1] + bs[2]) * (bs[0] + bs[1] + bs[2]);
for (int i = 0; i < 3; ++i) {
area -= bs[i] * bs[i];
}
assert(area % 2 == 0);
area /= 2;
const Mint ans = planePartition(bs[0], bs[1], bs[2]);
printf("%lld %u\n", area, ans.x);
}
#ifndef LOCAL
break;
#endif
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 137ms
memory: 120996kb
input:
6 2 1 2 1 1 137 3 94 95 3 1998 1996 998244 353999 999999 50 120 150
output:
7 4 4 1 1124 31585548 23951 33873190 1289433675488 748596399 23600 480090154
result:
ok 12 numbers
Test #2:
score: 0
Accepted
time: 115ms
memory: 120804kb
input:
9 3 3 3 1 1 1 3 3 3 1 1 1 3 3 3 2 2 2 3 3 3 2 2 2 3 3 3
output:
27 980 3 2 27 980 3 2 27 980 12 20 27 980 12 20 27 980
result:
ok 18 numbers
Test #3:
score: 0
Accepted
time: 127ms
memory: 120992kb
input:
10 4 4 4 3 3 3 1 1 1 2 2 2 4 4 4 4 4 4 2 2 2 4 4 4 4 4 4 3 3 3
output:
48 232848 27 980 3 2 12 20 48 232848 48 232848 12 20 48 232848 48 232848 27 980
result:
ok 20 numbers
Test #4:
score: 0
Accepted
time: 151ms
memory: 120752kb
input:
10 1 2 2 1 2 4 3 1 3 3 3 1 4 3 4 4 4 4 1 4 2 1 1 1 3 3 3 3 4 4
output:
7 4 8 1 11 6 11 6 39 14112 48 232848 8 1 3 2 27 980 39 14112
result:
ok 20 numbers
Test #5:
score: 0
Accepted
time: 123ms
memory: 120808kb
input:
10 3 100 100 3 98 100 3 45 54 3 56 57 3 79 80 3 99 97 3 2 2 3 5 8 3 89 87 3 95 95
output:
1191 386990672 1175 539161334 540 1 668 597802742 944 88504157 1163 413653028 15 20 60 1 1043 408813607 1131 489761860
result:
ok 20 numbers
Test #6:
score: 0
Accepted
time: 110ms
memory: 120720kb
input:
10 3 1000 1000 3 998 1000 3 450 540 3 569 570 3 799 800 1 999 999 3 200 200 3 797 800 2 984 985 2 797 797
output:
11991 368456334 11975 319484294 5400 1 6824 270662241 9584 777832912 3995 1998 2391 688129042 9564 1 7871 274044687 6372 931624591
result:
ok 20 numbers
Test #7:
score: 0
Accepted
time: 114ms
memory: 120724kb
input:
10 3 999 999 3 899 897 3 799 800 1 314 314 3 599 299 2 924 925 3 569 570 3 980 980 3 797 800 2 797 797
output:
11979 143556225 10763 789509419 9584 777832912 1255 628 3588 1 7391 55315847 6824 270662241 11751 764285985 9564 1 6372 931624591
result:
ok 20 numbers
Test #8:
score: 0
Accepted
time: 124ms
memory: 120740kb
input:
10 3 2831 2832 3 3641 3641 2 4958 4958 2 4757 4756 1 4234 4234 3 1294 1296 3 4865 3857 3 4598 4596 3 2 2 3 4983 4984
output:
33968 222796211 43683 991035937 39660 138057687 38047 734317385 16935 8468 15527 296868897 46284 1 55151 574369882 15 20 59792 628461191
result:
ok 20 numbers
Test #9:
score: 0
Accepted
time: 121ms
memory: 121004kb
input:
10 3 3795 3795 1 4353 4353 2 981 981 3 3865 3866 3 1998 1999 3 2345 2347 3 4759 4756 2 1245 1246 2 2385 3845 3 3771 3770
output:
45531 954169403 17411 8706 7844 23006980 46376 582135734 23972 914547013 28139 341107126 57072 1 9959 579653674 19080 1 45236 589619316
result:
ok 20 numbers
Test #10:
score: 0
Accepted
time: 125ms
memory: 120968kb
input:
10 24 24 24 42 42 42 77 77 77 17 17 17 59 59 59 15 15 15 90 90 90 47 47 47 75 75 75 20 20 20
output:
1728 252553554 5292 380589438 17787 42131906 867 739254462 10443 743809195 675 905920394 24300 754508597 6627 697962640 16875 698790321 1200 955417590
result:
ok 20 numbers
Test #11:
score: 0
Accepted
time: 128ms
memory: 120748kb
input:
10 37 37 37 46 46 46 43 43 43 19 19 19 49 49 49 9 9 9 17 17 17 92 92 92 50 50 50 100 100 100
output:
4107 893875715 6348 563300886 5547 881523094 1083 18413628 7203 426655263 243 768718993 867 739254462 25392 628099022 7500 962679491 30000 951252372
result:
ok 20 numbers
Test #12:
score: 0
Accepted
time: 113ms
memory: 120752kb
input:
10 73 48 54 59 50 76 61 26 86 37 82 65 47 85 41 59 67 41 95 9 100 83 36 13 45 69 38 98 75 88
output:
9527 931310010 10711 43770305 6343 171264608 9220 767263191 7699 896329424 8587 508764940 3404 65661300 1872 1 6644 849129742 22175 572662466
result:
ok 20 numbers
Test #13:
score: 0
Accepted
time: 122ms
memory: 120820kb
input:
10 97 64 36 37 33 62 44 31 31 5 59 28 20 65 78 16 16 12 79 79 8 40 94 58 79 70 10 19 54 20
output:
9207 81490618 4820 970364432 3520 167402772 560 1 5151 545988093 624 21656541 2464 897791557 9264 839387952 2799 903490208 1520 1
result:
ok 20 numbers
Test #14:
score: 0
Accepted
time: 113ms
memory: 121000kb
input:
10 47 53 38 49 75 90 64 18 30 68 68 25 64 23 81 91 30 54 34 63 26 56 88 86 98 95 71 72 26 90
output:
6120 788617201 13544 237562913 2160 1 6175 973411228 5852 421295168 6480 1 3536 1 16348 48494128 22356 283563258 7424 573058245
result:
ok 20 numbers
Test #15:
score: 0
Accepted
time: 133ms
memory: 120760kb
input:
10 37 44 98 19 26 35 36 16 4 92 23 40 38 36 84 55 78 82 47 49 30 94 70 28 32 14 22 56 29 81
output:
6512 1 1876 82651158 256 1 3680 1 5472 1 14559 715822037 4856 200224674 7824 456755437 1216 345513535 6480 57951855
result:
ok 20 numbers
Test #16:
score: 0
Accepted
time: 122ms
memory: 120760kb
input:
10 34401 34401 34401 98651 98651 98651 78629 78629 78629 65591 65591 65591 66046 66046 66046 52700 52700 52700 17307 17307 17307 33324 33324 33324 77617 77617 77617 99785 99785 99785
output:
3550286403 992487865 29196059403 420763712 18547558923 153343492 12906537843 81352952 13086222348 650486915 8331870000 97517555 898596747 225446043 3331466928 76350604 18073196067 435310816 29871138675 202468820
result:
ok 20 numbers
Test #17:
score: 0
Accepted
time: 102ms
memory: 120760kb
input:
10 3647 74898 74991 51941 70217 44785 51153 1620 52094 62267 51597 11976 65243 26874 45053 34401 98651 78629 65591 23554 66046 52700 17307 53332 77617 99785 74174 60382 17109 62860
output:
1079981108 105830078 8601983659 449437293 331010399 172379911 2469997052 138590448 4798341432 118890675 10612909275 674336947 5646157855 118586319 3370259975 895532073 20324029396 465558751 3918236391 22801073
result:
ok 20 numbers
Test #18:
score: 0
Accepted
time: 124ms
memory: 120760kb
input:
10 308 316 10 403 6 400 3 576 570 587 2 586 1000 1000 1 1 1 1000000 100 100 100 113 80 110 1000000 1 1 1 1000000 1
output:
12316 267213956 9591 969455325 6840 1 4687 268993924 3999 2000 4 1 30000 951252372 29271 43102189 4 1 4 1
result:
ok 20 numbers
Test #19:
score: 0
Accepted
time: 123ms
memory: 120988kb
input:
10 970 1 970 385 380 6 2 700 706 101 100 99 183 24 202 999999 1 1 1 1 999999 4 124830 2 832 2 12 133 77 77
output:
3879 1940 9119 735069937 5600 1 29996 869170008 17543 997671096 4 1 4 1 32 1 96 1 23275 627158815
result:
ok 20 numbers
Test #20:
score: 0
Accepted
time: 113ms
memory: 120848kb
input:
10 201572 201572 201572 590217 590217 590217 374643 374643 374643 92508 92508 92508 1000000 1000000 1000000 247427 247427 247427 774179 774179 774179 593157 593157 593157 751207 751207 751207 909474 909474 909474
output:
121893813552 326183328 1045068321267 365888698 421072132347 50616771 25673190192 945664445 3000000000000 142411650 183660360987 574138609 1798059372123 574598131 1055505679947 62300093 1692935870547 866008617 2481428870028 843792102
result:
ok 20 numbers
Test #21:
score: 0
Accepted
time: 122ms
memory: 120760kb
input:
10 599472 268253 682858 666172 689269 998823 625414 945281 370178 798580 246142 590665 32873 131908 130577 586779 319509 393463 725788 859892 283263 609870 959975 546223 852317 667850 648721 95783 486430 365205
output:
609064841975 344008598 1709510435148 90357106 923526818047 507519861 580088554191 528801354 16174933120 258991044 486935205419 235604800 800107137695 29002233 1294037814116 511457820 1517461502884 171449284 139921722060 1
result:
ok 20 numbers