QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #306752 | #838. Horrible Cycles | Mars_Dingdang | AC ✓ | 68ms | 5596kb | C++14 | 1.8kb | 2024-01-17 08:29:36 | 2024-01-17 08:29:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(ii,aa,bb) for(re int ii = aa; ii <= bb; ii++)
#define Rep(ii,aa,bb) for(re int ii = aa; ii >= bb; ii--)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int, int> PII;
const int maxn = 5005;
template <typename T>
inline void chkmax(T &x, T y) {x = (x > y ? x : y);}
template <typename T>
inline void chkmin(T &x, T y) {x = (x < y ? x : y);}
namespace IO_ReadWrite {
#define re register
#define gg (p1 == p2 && (p2 = (p1 = _buf) + fread(_buf, 1, 1<<21, stdin), p1 == p2) ? EOF :*p1++)
char _buf[1<<21], *p1 = _buf, *p2 = _buf;
template <typename T>
inline void read(T &x){
x = 0; re T f=1; re char c = gg;
while(c > 57 || c < 48){if(c == '-') f = -1;c = gg;}
while(c >= 48 &&c <= 57){x = (x<<1) + (x<<3) + (c^48);c = gg;}
x *= f;return;
}
inline void ReadChar(char &c){
c = gg;
while(!isalpha(c)) c = gg;
}
template <typename T>
inline void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x/10);
putchar('0' + x % 10);
}
template <typename T>
inline void writeln(T x){write(x); putchar('\n');}
}
using namespace IO_ReadWrite;
const ll mod = 998244353;
ll n, a[maxn], f[maxn];
inline ll Pow(ll a, ll b) {
ll res = 1;
while(b) {
if(b & 1) res = res * a % mod;
a = a *a % mod;
b >>= 1;
}
return res;
}
ll ans;
int main () {
read(n); rep(i, 1, n) read(a[i]);
sort(a + 1, a + n + 1);
f[0] = 1;
rep(i, 1, n) {
rep(k, 1, a[i] - a[i - 1]) {
Rep(j, n, 1) (f[j] += f[j - 1]) %= mod;
}
ans += f[1]; ans %= mod;
rep(j, 0, n - 1) (f[j] += f[j + 1] * (j + 1) * j % mod) %= mod;
}
rep(i, 1, n) ans -= a[i], ans %= mod;
writeln((ans * Pow(2, mod - 2) % mod + mod) % mod);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
input:
1 1
output:
0
result:
ok answer is '0'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
2 2 2
output:
1
result:
ok answer is '1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
3 3 3 2
output:
7
result:
ok answer is '7'
Test #4:
score: 0
Accepted
time: 1ms
memory: 5596kb
input:
10 6 6 7 7 8 8 9 9 10 10
output:
410150080
result:
ok answer is '410150080'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
25 19 5 16 16 19 22 13 15 19 25 1 24 7 2 4 24 3 19 1 5 5 6 19 8 18
output:
181693199
result:
ok answer is '181693199'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25
output:
833207138
result:
ok answer is '833207138'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3424kb
input:
50 31 15 36 25 26 32 26 22 50 49 41 36 49 35 39 18 2 3 23 18 33 15 1 45 4 47 36 34 23 3 49 16 29 48 27 25 33 15 40 3 50 50 40 14 49 36 31 6 22 1
output:
779170262
result:
ok answer is '779170262'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3420kb
input:
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
output:
688904780
result:
ok answer is '688904780'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3500kb
input:
250 138 96 246 191 156 238 201 242 233 23 236 77 26 206 203 116 18 160 164 248 249 10 220 228 125 210 172 128 127 152 209 6 79 25 164 177 87 40 57 113 203 155 57 203 99 45 221 240 244 32 238 122 138 86 237 149 19 175 215 94 212 121 245 199 234 8 46 218 204 138 206 48 162 94 238 184 120 159 57 228 14...
output:
49866440
result:
ok answer is '49866440'
Test #10:
score: 0
Accepted
time: 1ms
memory: 5540kb
input:
250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 ...
output:
658185020
result:
ok answer is '658185020'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
500 289 21 238 284 123 225 289 119 177 391 336 381 77 104 450 132 478 38 397 144 17 466 244 65 287 402 434 198 140 353 77 391 253 154 248 16 103 296 453 433 334 185 459 404 348 363 414 478 495 454 218 325 466 180 404 119 57 36 17 378 424 374 148 434 141 61 100 239 406 461 76 3 459 481 242 200 50 467...
output:
126505365
result:
ok answer is '126505365'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3428kb
input:
500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 ...
output:
675760977
result:
ok answer is '675760977'
Test #13:
score: 0
Accepted
time: 3ms
memory: 3644kb
input:
1000 894 197 325 232 902 183 41 481 495 266 152 704 790 458 546 258 30 366 747 546 332 816 523 683 771 152 647 967 785 793 62 915 864 667 972 536 678 183 290 164 533 374 932 943 508 627 226 823 644 596 767 620 563 613 53 340 813 164 591 752 990 342 326 157 97 25 197 373 732 224 693 539 826 835 642 9...
output:
846396949
result:
ok answer is '846396949'
Test #14:
score: 0
Accepted
time: 3ms
memory: 3440kb
input:
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 ...
output:
719983487
result:
ok answer is '719983487'
Test #15:
score: 0
Accepted
time: 7ms
memory: 3600kb
input:
1500 1411 757 1313 912 262 1187 981 1462 907 180 1271 1463 269 957 28 355 805 260 975 876 1029 1170 1019 672 337 54 835 1453 1037 1116 326 578 730 311 1089 1081 849 575 1143 948 814 599 304 1206 26 788 334 1109 361 176 614 866 77 993 441 886 814 824 125 89 1256 926 727 413 412 846 1112 1251 298 1472...
output:
557496101
result:
ok answer is '557496101'
Test #16:
score: 0
Accepted
time: 7ms
memory: 3492kb
input:
1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 ...
output:
275972573
result:
ok answer is '275972573'
Test #17:
score: 0
Accepted
time: 11ms
memory: 3600kb
input:
2000 271 1415 1493 921 895 953 585 322 909 77 1116 1803 892 964 1756 1407 1374 659 933 1341 1597 1828 1547 906 1573 133 1556 1421 104 1287 75 322 233 464 1519 1064 817 730 657 1075 126 1570 426 1434 1583 1785 1554 1978 1785 1126 906 1585 613 275 1475 1572 1167 764 581 505 1977 1539 281 1534 1766 185...
output:
101405198
result:
ok answer is '101405198'
Test #18:
score: 0
Accepted
time: 11ms
memory: 3528kb
input:
2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 2000 ...
output:
404199111
result:
ok answer is '404199111'
Test #19:
score: 0
Accepted
time: 26ms
memory: 3580kb
input:
3000 2457 2825 1854 314 2080 2212 320 163 220 888 1273 310 401 1661 1965 2955 717 2464 1527 329 565 2544 1083 538 79 305 274 2068 830 76 793 433 2602 2861 2873 1399 2149 1380 2217 2986 422 1661 1624 2117 1954 1136 2075 133 414 2145 1853 1062 854 2129 2090 2995 1930 2659 2379 2258 2259 2328 1749 1910...
output:
573272276
result:
ok answer is '573272276'
Test #20:
score: 0
Accepted
time: 25ms
memory: 3480kb
input:
3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 ...
output:
354414340
result:
ok answer is '354414340'
Test #21:
score: 0
Accepted
time: 44ms
memory: 3600kb
input:
4000 2643 2747 3318 1706 3072 1279 1863 2197 3530 3891 2533 2305 2502 1463 1471 1911 3869 1757 2713 3828 2126 1260 106 3657 585 3774 991 2522 853 1570 2614 32 970 1851 420 2631 2584 1630 1584 3600 2015 1752 821 1904 2133 998 2596 2992 3555 3164 288 1323 1800 1791 3808 1714 3284 42 880 1419 2734 333 ...
output:
787769330
result:
ok answer is '787769330'
Test #22:
score: 0
Accepted
time: 44ms
memory: 3496kb
input:
4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 4000 ...
output:
282890964
result:
ok answer is '282890964'
Test #23:
score: 0
Accepted
time: 68ms
memory: 3620kb
input:
5000 2829 1670 679 1395 65 1242 1599 3742 4840 3702 1201 812 603 3457 1385 2163 3509 1562 603 2624 2390 2464 4938 4289 3091 3754 2900 4169 1387 2359 3628 1143 4339 2544 4775 863 1915 4473 3847 2807 4311 3652 4611 99 504 4157 4925 4851 2696 2399 2234 2096 2553 3645 3934 2946 1047 642 1678 172 2721 48...
output:
635598407
result:
ok answer is '635598407'
Test #24:
score: 0
Accepted
time: 68ms
memory: 3564kb
input:
5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 ...
output:
74560349
result:
ok answer is '74560349'
Test #25:
score: 0
Accepted
time: 68ms
memory: 3508kb
input:
5000 1 2 3 3 5 6 7 6 6 2 7 8 8 7 10 3 15 8 19 4 1 14 8 17 16 24 18 25 28 29 4 15 8 22 30 23 31 15 32 7 8 8 36 15 34 43 16 3 40 49 3 52 38 39 44 42 31 44 59 52 41 40 57 38 41 38 46 43 16 26 61 49 33 57 38 63 28 76 32 18 58 63 43 40 85 39 48 43 88 71 41 68 88 53 43 62 57 77 60 51 24 20 61 58 33 41 23 ...
output:
414429770
result:
ok answer is '414429770'