QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#80206 | #2618. Casual Dancers | woxiangbaile# | AC ✓ | 1281ms | 36900kb | C++14 | 5.3kb | 2023-02-23 08:41:21 | 2023-02-23 08:41:23 |
Judging History
answer
#include <cstdio>
#define rep(i, d, u) for(int i = d; i <= u; ++i)
#define dep(i, u, d) for(int i = u; i >= d; --i)
int ured() {
int re = 0;
char ch;
do {
ch = getchar();
} while('9' < ch || ch < '0');
do {
re = re * 10 + (ch ^ '0');
} while('0' <= (ch = getchar()) && ch <= '9');
return re;
}
int ired() {
int re = 0;
char ch;
bool st = 0;
do {
ch = getchar();
} while(('9' < ch || ch < '0') && ch != '-');
if(ch == '-') {
ch = getchar(), st = 1;
}
do {
re = re * 10 + (ch ^ '0');
} while('0' <= (ch = getchar()) && ch <= '9');
return st ? -re : re;
}
void uwit(int da) {
int ch[21], cn = 0;
do {
ch[++cn] = da - da / 10 * 10;
} while(da /= 10);
do {
putchar('0' ^ ch[cn]);
} while(--cn);
}
int min(int le, int ri) {
return le < ri ? le : ri;
}
void swap(int &le, int &ri) {
int tp = le;
le = ri, ri = tp;
}
const int _maxn = 400011, _maxb = 31, _mods = 998244353;
int qpow(int da, int up) {
int re = 1;
while(up) {
if(up & 1) {
re = 1ll * re * da % _mods;
}
da = 1ll * da * da % _mods, up >>= 1;
}
return re;
}
void ince(int &le, int ri) {
if((le += ri) >= _mods) {
le -= _mods;
}
}
int incd(int le, int ri) {
return le + ri >= _mods ? le + ri - _mods : le + ri;
}
int decd(int le, int ri) {
return le - ri < 0 ? le - ri + _mods : le - ri;
}
int gpow[31], ginv[31], gpod[_maxn << 3], gind[_maxn << 3], lens, into[_maxn << 2];
void yclg() {
gpow[23] = 15311432, ginv[23] = 469870224;
dep(i, 22, 0) {
gpow[i] = 1ll * gpow[i + 1] * gpow[i + 1] % _mods, ginv[i] = 1ll * ginv[i + 1] * ginv[i + 1] % _mods;
}
}
void fini(int cn) {
for(lens = 1; lens < cn; lens <<= 1);
for(int i = 1, j = 1; i < lens; i <<= 1, ++j) {
if(!gpod[i]) {
gpod[i] = gind[i] = 1;
rep(k, i + 1, (i << 1) - 1) {
gpod[k] = 1ll * gpod[k - 1] * gpow[j] % _mods, gind[k] = 1ll * gind[k - 1] * ginv[j] % _mods;
}
}
}
rep(i, 1, lens - 2) {
into[i] = into[i >> 1] >> 1 | (i & 1 ? lens >> 1 : 0);
}
}
void fntt(int *fr, bool st) {
rep(i, 1, lens - 2) {
if(i < into[i]) {
swap(fr[i], fr[into[i]]);
}
}
int rg, *po;
for(int i = 1, j = 1; i < lens; i <<= 1, ++j) {
for(int k = 0; k < lens; k += i << 1) {
po = (st ? gpod + i : gind + i);
rep(l, k, k + i - 1) {
fr[l + i] = decd(fr[l], rg = 1ll * fr[l + i] * *po++ % _mods), ince(fr[l], rg);
}
}
}
if(!st) {
rg = qpow(lens, _mods - 2);
rep(i, 0, lens - 1) {
fr[i] = 1ll * fr[i] * rg % _mods;
}
}
}
void fcpy(int *fr, int *re, int ln) {
rep(i, 0, ln - 1) {
re[i] = fr[i];
}
}
void fclr(int *re, int ln) {
rep(i, 0, ln - 1) {
re[i] = 0;
}
}
void ftim(int *le, int *ri, int *re) {
rep(i, 0, lens - 1) {
re[i] = 1ll * le[i] * ri[i] % _mods;
}
}
int cpyl[_maxn << 2], cpyr[_maxn << 2];
void fcal(int *le, int *ri, int *re, int ln, int rn, int en) {
fini(ln + rn - 1), fcpy(le, cpyl, ln), fclr(cpyl + ln, lens - ln), fcpy(ri, cpyr, rn), fclr(cpyr + rn, lens - rn);
fntt(cpyl, 1), fntt(cpyr, 1), ftim(cpyl, cpyr, cpyl), fntt(cpyl, 0), fcpy(cpyl, re, en);
}
int cpya[_maxn << 2], cpyb[_maxn << 2];
void finv(int *fr, int *re, int ln) {
int ri;
re[0] = qpow(fr[0], _mods - 2);
for(int i = 1; i < ln; i <<= 1) {
fini(i << 1), ri = min(i << 1, ln);
fcpy(fr, cpya, ri), fclr(cpya + ri, lens - ri), fcpy(re, cpyb, i), fclr(cpyb + i, lens - i);
fntt(cpya, 1), fntt(cpyb, 1), ftim(cpya, cpyb, cpya), fntt(cpya, 0), fclr(cpya, i);
fntt(cpya, 1), ftim(cpya, cpyb, cpya), fntt(cpya, 0);
rep(j, i, ri - 1) {
re[j] = _mods - cpya[j];
}
}
}
int ycln[_maxn << 2], cpyc[_maxn << 2], cpyd[_maxn << 2];
void fcdq(int *re, int le, int ri) {
if(le + 1 == ri) {
if(le) {
re[le] = 1ll * re[le] * ycln[le] % _mods;
} else {
re[le] = 1;
}
} else {
fcdq(re, le, le + ri >> 1), fcal(cpyc, re + le, cpyd, ri - le, (ri + le >> 1) - le, ri - le);
rep(i, le + ri >> 1, ri - 1) {
ince(re[i], cpyd[i - le]);
}
fcdq(re, le + ri >> 1, ri);
}
}
void fexp(int *fr, int *re, int ln) {
rep(i, 0, ln - 1) {
cpyc[i] = 1ll * i * fr[i] % _mods, re[i] = 0;
}
fcdq(re, 0, ln);
}
void fder(int *re, int ln) {
rep(i, 0, ln - 2) {
re[i] = 1ll * (i + 1) * re[i + 1] % _mods;
}
re[ln - 1] = 0;
}
void fint(int *re, int ln) {
dep(i, ln - 1, 1) {
re[i] = 1ll * ycln[i] * re[i - 1] % _mods;
}
re[0] = 0;
}
int cpyf[_maxn << 2], cpyg[_maxn << 2];
void fqln(int *fr, int *re, int ln) {
fcpy(fr, cpyf, ln), fder(cpyf, ln), finv(fr, cpyg, ln), fcal(cpyf, cpyg, re, ln - 1, ln, ln), fint(re, ln);
}
int cpyh[_maxn << 2];
void fpow(int *fr, int *re, int up, int ln) {
fqln(fr, cpyh, ln);
rep(i, 0, ln - 1) {
cpyh[i] = 1ll * cpyh[i] * up % _mods;
}
fexp(cpyh, re, ln);
}
int abs(int da) {
return da < 0 ? -da : da;
}
int xf, xs, xt, n, datf[_maxn], dats[_maxn];
int solv(int da) {
int re = 0;
rep(i, 0, n << 1) {
re = (1ll * abs(n - da - i) * dats[i] + re) % _mods;
}
return 1ll * re * qpow(3, _mods - n - 1) % _mods;
}
int main() {
xf = ired(), xs = ired(), xt = ired(), n = ured(), yclg(), ycln[1] = 1;
rep(i, 2, n << 1) {
ycln[i] = _mods - 1ll * _mods / i * ycln[_mods % i] % _mods;
}
datf[0] = datf[1] = datf[2] = 1, fpow(datf, dats, n, n << 1 | 1);
uwit((0ll + solv(abs(xf - xs)) + solv(abs(xf - xt)) + solv(abs(xs - xt))) * (_mods + 1 >> 1) % _mods), putchar('\n');
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3376kb
input:
0 0 0 1 58
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3376kb
input:
1 2 2 1 100
output:
332748119
result:
ok 1 number(s): "332748119"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3316kb
input:
5 2 3 4 50
output:
160212060
result:
ok 1 number(s): "160212060"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3376kb
input:
-2 -1 1 2 71
output:
443664160
result:
ok 1 number(s): "443664160"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3344kb
input:
-1 0 -1 4 8
output:
751764268
result:
ok 1 number(s): "751764268"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3348kb
input:
-2 -2 2 5 54
output:
801060288
result:
ok 1 number(s): "801060288"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3424kb
input:
-2 2 4 8 36
output:
353135983
result:
ok 1 number(s): "353135983"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3424kb
input:
8 -7 1 7 28
output:
15
result:
ok 1 number(s): "15"
Test #9:
score: 0
Accepted
time: 1ms
memory: 3344kb
input:
-7 -8 0 16 54
output:
159363041
result:
ok 1 number(s): "159363041"
Test #10:
score: 0
Accepted
time: 1ms
memory: 3432kb
input:
5 11 -11 9 32
output:
717226646
result:
ok 1 number(s): "717226646"
Test #11:
score: 0
Accepted
time: 1ms
memory: 3320kb
input:
-16 1 -9 32 8
output:
855967855
result:
ok 1 number(s): "855967855"
Test #12:
score: 0
Accepted
time: 1ms
memory: 3320kb
input:
-13 28 28 37 80
output:
116405794
result:
ok 1 number(s): "116405794"
Test #13:
score: 0
Accepted
time: 2ms
memory: 3356kb
input:
6 26 -25 64 21
output:
91053409
result:
ok 1 number(s): "91053409"
Test #14:
score: 0
Accepted
time: 1ms
memory: 1752kb
input:
-39 23 1 31 64
output:
742331784
result:
ok 1 number(s): "742331784"
Test #15:
score: 0
Accepted
time: 1ms
memory: 1736kb
input:
-32 42 43 128 87
output:
57822539
result:
ok 1 number(s): "57822539"
Test #16:
score: 0
Accepted
time: 0ms
memory: 1476kb
input:
-80 55 -106 142 29
output:
435655440
result:
ok 1 number(s): "435655440"
Test #17:
score: 0
Accepted
time: 1ms
memory: 1728kb
input:
0 -83 -106 256 55
output:
120508896
result:
ok 1 number(s): "120508896"
Test #18:
score: 0
Accepted
time: 0ms
memory: 1880kb
input:
-100 -123 -167 91 74
output:
285780715
result:
ok 1 number(s): "285780715"
Test #19:
score: 0
Accepted
time: 2ms
memory: 1496kb
input:
252 -176 -239 512 49
output:
835642397
result:
ok 1 number(s): "835642397"
Test #20:
score: 0
Accepted
time: 3ms
memory: 1552kb
input:
-37 -124 151 867 76
output:
225290884
result:
ok 1 number(s): "225290884"
Test #21:
score: 0
Accepted
time: 4ms
memory: 1500kb
input:
-316 149 -149 1024 87
output:
374987754
result:
ok 1 number(s): "374987754"
Test #22:
score: 0
Accepted
time: 4ms
memory: 1520kb
input:
370 545 81 1073 69
output:
943329809
result:
ok 1 number(s): "943329809"
Test #23:
score: 0
Accepted
time: 7ms
memory: 1720kb
input:
-81 182 532 2048 87
output:
843173062
result:
ok 1 number(s): "843173062"
Test #24:
score: 0
Accepted
time: 1ms
memory: 1504kb
input:
-1229 -1607 319 199 24
output:
1926
result:
ok 1 number(s): "1926"
Test #25:
score: 0
Accepted
time: 10ms
memory: 1988kb
input:
43 -419 -613 4096 46
output:
418220629
result:
ok 1 number(s): "418220629"
Test #26:
score: 0
Accepted
time: 8ms
memory: 1912kb
input:
3434 -3146 -1774 2601 46
output:
705802517
result:
ok 1 number(s): "705802517"
Test #27:
score: 0
Accepted
time: 32ms
memory: 2648kb
input:
2193 -2331 2901 8192 75
output:
728593792
result:
ok 1 number(s): "728593792"
Test #28:
score: 0
Accepted
time: 4ms
memory: 1584kb
input:
233 -4307 -4363 1093 81
output:
303899847
result:
ok 1 number(s): "303899847"
Test #29:
score: 0
Accepted
time: 62ms
memory: 4080kb
input:
-4522 762 8059 16384 34
output:
190696426
result:
ok 1 number(s): "190696426"
Test #30:
score: 0
Accepted
time: 122ms
memory: 5740kb
input:
-5155 -3639 15798 24822 55
output:
808461103
result:
ok 1 number(s): "808461103"
Test #31:
score: 0
Accepted
time: 136ms
memory: 6764kb
input:
15234 4368 12248 32768 19
output:
115861480
result:
ok 1 number(s): "115861480"
Test #32:
score: 0
Accepted
time: 148ms
memory: 9864kb
input:
820 30492 3951 42789 76
output:
826647308
result:
ok 1 number(s): "826647308"
Test #33:
score: 0
Accepted
time: 323ms
memory: 12144kb
input:
1372 -24835 -24597 65536 65
output:
355997764
result:
ok 1 number(s): "355997764"
Test #34:
score: 0
Accepted
time: 371ms
memory: 18328kb
input:
-59726 17559 -45875 87143 58
output:
326130350
result:
ok 1 number(s): "326130350"
Test #35:
score: 0
Accepted
time: 658ms
memory: 22836kb
input:
-27584 51950 23030 131072 74
output:
325794325
result:
ok 1 number(s): "325794325"
Test #36:
score: 0
Accepted
time: 723ms
memory: 34972kb
input:
61155 52006 74974 164861 5
output:
160748350
result:
ok 1 number(s): "160748350"
Test #37:
score: 0
Accepted
time: 1227ms
memory: 36900kb
input:
41344 -81596 -95774 200000 59
output:
965482998
result:
ok 1 number(s): "965482998"
Test #38:
score: 0
Accepted
time: 113ms
memory: 5708kb
input:
42056 -90767 -54649 24350 63
output:
132823
result:
ok 1 number(s): "132823"
Test #39:
score: 0
Accepted
time: 1228ms
memory: 36812kb
input:
-74335 43393 57021 199994 67
output:
310210583
result:
ok 1 number(s): "310210583"
Test #40:
score: 0
Accepted
time: 706ms
memory: 33316kb
input:
-80838 73772 -18618 134415 57
output:
346157175
result:
ok 1 number(s): "346157175"
Test #41:
score: 0
Accepted
time: 1211ms
memory: 36816kb
input:
37457 74497 -81166 199997 59
output:
26667908
result:
ok 1 number(s): "26667908"
Test #42:
score: 0
Accepted
time: 752ms
memory: 34856kb
input:
31109 -65140 -77085 162412 46
output:
12858959
result:
ok 1 number(s): "12858959"
Test #43:
score: 0
Accepted
time: 1274ms
memory: 36824kb
input:
-58550 -97769 66373 199995 86
output:
789346262
result:
ok 1 number(s): "789346262"
Test #44:
score: 0
Accepted
time: 615ms
memory: 20352kb
input:
7739 58831 72332 124270 16
output:
167162440
result:
ok 1 number(s): "167162440"
Test #45:
score: 0
Accepted
time: 1243ms
memory: 36812kb
input:
-97901 25173 -99145 199999 52
output:
797290311
result:
ok 1 number(s): "797290311"
Test #46:
score: 0
Accepted
time: 591ms
memory: 20568kb
input:
-87118 -60882 -86669 126103 23
output:
487838027
result:
ok 1 number(s): "487838027"
Test #47:
score: 0
Accepted
time: 1225ms
memory: 36900kb
input:
-71646 69885 70206 200000 27
output:
285981891
result:
ok 1 number(s): "285981891"
Test #48:
score: 0
Accepted
time: 612ms
memory: 19992kb
input:
14475 -77173 -5177 117777 51
output:
251933976
result:
ok 1 number(s): "251933976"
Test #49:
score: 0
Accepted
time: 1265ms
memory: 36820kb
input:
-35780 37165 54712 199996 14
output:
763964192
result:
ok 1 number(s): "763964192"
Test #50:
score: 0
Accepted
time: 570ms
memory: 19172kb
input:
15709 -72676 -22298 101968 17
output:
406652317
result:
ok 1 number(s): "406652317"
Test #51:
score: 0
Accepted
time: 1233ms
memory: 36888kb
input:
74572 -98701 -56974 199991 62
output:
55467556
result:
ok 1 number(s): "55467556"
Test #52:
score: 0
Accepted
time: 718ms
memory: 35168kb
input:
-14644 -10031 -50353 168383 43
output:
376814948
result:
ok 1 number(s): "376814948"
Test #53:
score: 0
Accepted
time: 1224ms
memory: 36812kb
input:
22388 51898 80903 199995 89
output:
832434478
result:
ok 1 number(s): "832434478"
Test #54:
score: 0
Accepted
time: 589ms
memory: 20552kb
input:
34062 -76211 -25545 127193 91
output:
234760702
result:
ok 1 number(s): "234760702"
Test #55:
score: 0
Accepted
time: 1262ms
memory: 36816kb
input:
-19645 -45450 -16512 200000 77
output:
759439547
result:
ok 1 number(s): "759439547"
Test #56:
score: 0
Accepted
time: 74ms
memory: 5452kb
input:
98957 80512 -24606 20311 30
output:
985804570
result:
ok 1 number(s): "985804570"
Test #57:
score: 0
Accepted
time: 1216ms
memory: 36892kb
input:
-87259 -11505 14596 199994 83
output:
160520754
result:
ok 1 number(s): "160520754"
Test #58:
score: 0
Accepted
time: 1226ms
memory: 36892kb
input:
0 0 0 200000 0
output:
393458944
result:
ok 1 number(s): "393458944"
Test #59:
score: 0
Accepted
time: 1222ms
memory: 36816kb
input:
0 0 0 200000 100
output:
393458944
result:
ok 1 number(s): "393458944"
Test #60:
score: 0
Accepted
time: 1224ms
memory: 36808kb
input:
-100000 -100000 -100000 200000 75
output:
393458944
result:
ok 1 number(s): "393458944"
Test #61:
score: 0
Accepted
time: 1261ms
memory: 36888kb
input:
100000 100000 100000 200000 63
output:
393458944
result:
ok 1 number(s): "393458944"
Test #62:
score: 0
Accepted
time: 1273ms
memory: 36812kb
input:
100000 0 -100000 200000 56
output:
678255914
result:
ok 1 number(s): "678255914"
Test #63:
score: 0
Accepted
time: 1281ms
memory: 36812kb
input:
0 1 2 200000 22
output:
630634769
result:
ok 1 number(s): "630634769"
Test #64:
score: 0
Accepted
time: 1ms
memory: 1736kb
input:
100000 0 -100000 1 32
output:
200000
result:
ok 1 number(s): "200000"
Test #65:
score: 0
Accepted
time: 1ms
memory: 1740kb
input:
100000 100000 100000 1 33
output:
1
result:
ok 1 number(s): "1"
Test #66:
score: 0
Accepted
time: 1ms
memory: 1756kb
input:
-100000 -100000 -100000 1 6
output:
1
result:
ok 1 number(s): "1"
Test #67:
score: 0
Accepted
time: 1ms
memory: 1548kb
input:
100000 100000 -100000 1 7
output:
332948118
result:
ok 1 number(s): "332948118"
Test #68:
score: 0
Accepted
time: 1ms
memory: 1744kb
input:
-100000 -100000 100000 1 40
output:
332948118
result:
ok 1 number(s): "332948118"
Test #69:
score: 0
Accepted
time: 1ms
memory: 1764kb
input:
100000 -100000 -100000 100 63
output:
764105630
result:
ok 1 number(s): "764105630"
Test #70:
score: 0
Accepted
time: 1ms
memory: 1480kb
input:
-100000 100000 100000 100 13
output:
764105630
result:
ok 1 number(s): "764105630"
Test #71:
score: 0
Accepted
time: 0ms
memory: 1692kb
input:
-100000 100000 0 100 10
output:
200000
result:
ok 1 number(s): "200000"
Test #72:
score: 0
Accepted
time: 555ms
memory: 19060kb
input:
-100000 100000 0 99999 77
output:
200000
result:
ok 1 number(s): "200000"
Test #73:
score: 0
Accepted
time: 566ms
memory: 19140kb
input:
-100000 100000 0 100000 80
output:
200000
result:
ok 1 number(s): "200000"
Test #74:
score: 0
Accepted
time: 557ms
memory: 19144kb
input:
-100000 100000 0 100001 5
output:
50125708
result:
ok 1 number(s): "50125708"