QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#80206#2618. Casual Dancerswoxiangbaile#AC ✓1281ms36900kbC++145.3kb2023-02-23 08:41:212023-02-23 08:41:23

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-23 08:41:23]
  • Judged
  • Verdict: AC
  • Time: 1281ms
  • Memory: 36900kb
  • [2023-02-23 08:41:21]
  • Submitted

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"