QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#563114 | #4011. 计算几何 | Elegia | 100 ✓ | 109ms | 97452kb | C++23 | 1.6kb | 2024-09-14 02:49:14 | 2024-09-14 02:49:15 |
Judging History
answer
/*
飞过天际 走到海角 要拾回快乐
双手摸索 双眼搜索 我尚有感觉
心似刀割 总算醒觉 胜地难闭幕
失去感觉 失去知觉 我尚有躯壳
*/
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
// https://loj.ac/s/498386
namespace loj6677 {
const int N = 6000054, mod = 998244353;
int fact[N], finv[N];
int pact[N], pinv[N];
ull PowerMod(ull a, int n, ull c = 1) {for (; n; n >>= 1, a = a * a % mod) if (n & 1) c = c * a % mod; return c;}
void init(int n) {
int i;
for (*fact = i = 1; i <= n; ++i) fact[i] = (ull)fact[i - 1] * i % mod;
finv[n] = PowerMod(fact[n], mod - 2);
for (i = n; i; --i) finv[i - 1] = (ull)finv[i] * i % mod;
for (*pact = i = 1; i <= n; ++i) pact[i] = (ull)pact[i - 1] * fact[i] % mod;
pinv[n] = PowerMod(pact[n], mod - 2);
for (i = n; i; --i) pinv[i - 1] = (ull)pinv[i] * fact[i] % mod;
}
int query(int a, int b, int c) {
if (!a || !b || !c) return 1;
return (ull)pact[a + b + c - 1] * pinv[a + b - 1] % mod * pinv[b + c - 1] % mod * pinv[c + a - 1] % mod * pact[a - 1] % mod * pact[b - 1] % mod * pact[c - 1] % mod;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
loj6677::init(6e6);
while (T--) {
int x, y, z; cin >> x >> y >> z;
if (x < y) swap(x, y);
if (x < z) swap(x, z);
x = min(x, y + z);
int A = x + y - z, B = y + z - x, C = z + x - y;
ull ans1 = A * (ull)B + B * (ull)C + C * (ull)A;
cout << ans1 << ' ' << loj6677::query(A, B, C) << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 5
Accepted
time: 98ms
memory: 97444kb
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 9 lines
Test #2:
score: 5
Accepted
time: 96ms
memory: 97424kb
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 10 lines
Test #3:
score: 5
Accepted
time: 85ms
memory: 97392kb
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 10 lines
Test #4:
score: 5
Accepted
time: 97ms
memory: 97372kb
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 10 lines
Test #5:
score: 5
Accepted
time: 97ms
memory: 97384kb
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 10 lines
Test #6:
score: 5
Accepted
time: 89ms
memory: 97328kb
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 10 lines
Test #7:
score: 5
Accepted
time: 97ms
memory: 97392kb
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 10 lines
Test #8:
score: 5
Accepted
time: 84ms
memory: 97324kb
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 10 lines
Test #9:
score: 5
Accepted
time: 99ms
memory: 97328kb
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 10 lines
Test #10:
score: 5
Accepted
time: 85ms
memory: 97376kb
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 10 lines
Test #11:
score: 5
Accepted
time: 94ms
memory: 97392kb
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 10 lines
Test #12:
score: 5
Accepted
time: 96ms
memory: 97384kb
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 10 lines
Test #13:
score: 5
Accepted
time: 88ms
memory: 97328kb
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 10 lines
Test #14:
score: 5
Accepted
time: 88ms
memory: 97324kb
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 10 lines
Test #15:
score: 5
Accepted
time: 91ms
memory: 97452kb
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 10 lines
Test #16:
score: 5
Accepted
time: 91ms
memory: 97308kb
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 10 lines
Test #17:
score: 5
Accepted
time: 90ms
memory: 97360kb
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 10 lines
Test #18:
score: 5
Accepted
time: 99ms
memory: 97324kb
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 10 lines
Test #19:
score: 5
Accepted
time: 109ms
memory: 97384kb
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 10 lines
Test #20:
score: 5
Accepted
time: 94ms
memory: 97312kb
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 10 lines
Extra Test:
score: 0
Extra Test Passed