QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#290474#4841. Geometryucup-team087#AC ✓96ms121052kbC++145.8kb2023-12-25 01:57:392023-12-25 01:57:40

Judging History

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

  • [2023-12-25 01:57:40]
  • 评测
  • 测评结果:AC
  • 用时:96ms
  • 内存:121052kb
  • [2023-12-25 01:57:39]
  • 提交

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;
}

详细

Test #1:

score: 100
Accepted
time: 76ms
memory: 120752kb

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: 89ms
memory: 120768kb

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: 83ms
memory: 120820kb

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: 79ms
memory: 120748kb

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: 90ms
memory: 120892kb

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: 92ms
memory: 121036kb

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: 96ms
memory: 121052kb

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: 92ms
memory: 121048kb

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: 72ms
memory: 120820kb

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: 91ms
memory: 120828kb

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: 79ms
memory: 121040kb

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: 83ms
memory: 121040kb

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: 80ms
memory: 120816kb

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: 67ms
memory: 120816kb

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: 81ms
memory: 121048kb

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: 81ms
memory: 120816kb

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: 81ms
memory: 120816kb

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: 93ms
memory: 120816kb

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: 75ms
memory: 121052kb

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: 60ms
memory: 120900kb

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: 83ms
memory: 120820kb

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