QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#832340#2618. Casual DancersAuroreAC ✓3425ms135120kbC++232.2kb2024-12-25 20:38:282024-12-25 20:38:30

Judging History

This is the latest submission verdict.

  • [2024-12-25 20:38:30]
  • Judged
  • Verdict: AC
  • Time: 3425ms
  • Memory: 135120kb
  • [2024-12-25 20:38:28]
  • Submitted

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int buf[30];
inline void print(int x,char ch=' '){
	if(x<0) putchar('-'),x=-x;
	int tot=0;
	do{
		buf[++tot]=x%10;
		x/=10;
	}while(x);
	for(int i=tot;i;i--)
		putchar(buf[i]+'0');
	putchar(ch);
}
const int MAXN=1e7+5,mod=998244353,G=3,Gi=332748118;
int qpow(int a,int b){
	int ans=1,base=a;
	while(b){
		if(b&1) ans=ans*base%mod;
		base=base*base%mod;
		b>>=1;
	}
	return ans;
}
int A[MAXN],B[MAXN],limit,r[MAXN];
void ntt(int *f,int flag){
	for(int i=0;i<limit;i++)
		if(i<r[i]) swap(f[i],f[r[i]]);
	for(int len=2;len<=limit;len<<=1){
		int mid=len>>1,wn=qpow(flag?G:Gi,(mod-1)/len);
		for(int i=0;i<limit;i+=len)
			for(int j=0,w=1;j<mid;j++,w=w*wn%mod){
				int x=f[i+j],y=f[i+j+mid]*w%mod;
				f[i+j]=(x+y)%mod;
				f[i+j+mid]=(x-y+mod)%mod;
			}
	}
}
vector<int> merge(vector<int> a,vector<int> b){
	int n=a.size()-1,m=b.size()-1;
	for(limit=1;limit<=n+m;limit<<=1);
	for(int i=0;i<limit;i++){
		r[i]=((r[i>>1]>>1)|((i&1)?limit>>1:0));
		A[i]=B[i]=0;
	}
	for(int i=0;i<=n;i++) A[i]=a[i];
	for(int i=0;i<=m;i++) B[i]=b[i];
	ntt(A,0),ntt(B,0);
	for(int i=0;i<limit;i++) A[i]=A[i]*B[i]%mod;
	ntt(A,1);
	int inv=qpow(limit,mod-2);
	vector<int> c;
	for(int i=0;i<=n+m;i++) c.push_back(A[i]*inv%mod);
	return c;
}

const int N=2e5+5;
vector<int> t[N<<2];
int tag[MAXN<<2];
void dfs(int i,int l,int r){
	if(l==r){
		if(l==0){
			t[i].assign(1,1);
			tag[i]=0;
		}
		else{
			t[i].assign(3,Gi);
			tag[i]=-1;
		}
		return ;
	}
	int mid=(l+r-1)>>1;
	dfs(i<<1,l,mid);
	dfs(i<<1|1,mid+1,r);
	t[i]=merge(t[i<<1],t[i<<1|1]);
	tag[i]=tag[i<<1]+tag[i<<1|1];
}
int solve(int n,int k){
	dfs(1,0,k);
	tag[1]+=n;
	int ans=0;
	for(int i=0;i<t[1].size();i++){
		int dist=tag[1]+i;
		ans=(ans+abs(dist)*t[1][i])%mod;
	}
	return ans;
}
signed main(){
	int x=read(),y=read(),z=read();
	int k=read(),p=read();
	int ans=solve(abs(x-y),k)+solve(abs(x-z),k)+solve(abs(y-z),k);
	print(ans*(mod+1)/2%mod);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 7952kb

input:

0 0 0
1
58

output:

1 

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 1ms
memory: 7660kb

input:

1 2 2
1
100

output:

332748119 

result:

ok 1 number(s): "332748119"

Test #3:

score: 0
Accepted
time: 2ms
memory: 7948kb

input:

5 2 3
4
50

output:

160212060 

result:

ok 1 number(s): "160212060"

Test #4:

score: 0
Accepted
time: 2ms
memory: 7916kb

input:

-2 -1 1
2
71

output:

443664160 

result:

ok 1 number(s): "443664160"

Test #5:

score: 0
Accepted
time: 0ms
memory: 7712kb

input:

-1 0 -1
4
8

output:

751764268 

result:

ok 1 number(s): "751764268"

Test #6:

score: 0
Accepted
time: 1ms
memory: 7716kb

input:

-2 -2 2
5
54

output:

801060288 

result:

ok 1 number(s): "801060288"

Test #7:

score: 0
Accepted
time: 1ms
memory: 7712kb

input:

-2 2 4
8
36

output:

353135983 

result:

ok 1 number(s): "353135983"

Test #8:

score: 0
Accepted
time: 2ms
memory: 7956kb

input:

8 -7 1
7
28

output:

15 

result:

ok 1 number(s): "15"

Test #9:

score: 0
Accepted
time: 2ms
memory: 7720kb

input:

-7 -8 0
16
54

output:

159363041 

result:

ok 1 number(s): "159363041"

Test #10:

score: 0
Accepted
time: 1ms
memory: 7720kb

input:

5 11 -11
9
32

output:

717226646 

result:

ok 1 number(s): "717226646"

Test #11:

score: 0
Accepted
time: 2ms
memory: 7660kb

input:

-16 1 -9
32
8

output:

855967855 

result:

ok 1 number(s): "855967855"

Test #12:

score: 0
Accepted
time: 2ms
memory: 7964kb

input:

-13 28 28
37
80

output:

116405794 

result:

ok 1 number(s): "116405794"

Test #13:

score: 0
Accepted
time: 2ms
memory: 7744kb

input:

6 26 -25
64
21

output:

91053409 

result:

ok 1 number(s): "91053409"

Test #14:

score: 0
Accepted
time: 0ms
memory: 7960kb

input:

-39 23 1
31
64

output:

742331784 

result:

ok 1 number(s): "742331784"

Test #15:

score: 0
Accepted
time: 2ms
memory: 7816kb

input:

-32 42 43
128
87

output:

57822539 

result:

ok 1 number(s): "57822539"

Test #16:

score: 0
Accepted
time: 3ms
memory: 7776kb

input:

-80 55 -106
142
29

output:

435655440 

result:

ok 1 number(s): "435655440"

Test #17:

score: 0
Accepted
time: 2ms
memory: 7668kb

input:

0 -83 -106
256
55

output:

120508896 

result:

ok 1 number(s): "120508896"

Test #18:

score: 0
Accepted
time: 2ms
memory: 7688kb

input:

-100 -123 -167
91
74

output:

285780715 

result:

ok 1 number(s): "285780715"

Test #19:

score: 0
Accepted
time: 7ms
memory: 8220kb

input:

252 -176 -239
512
49

output:

835642397 

result:

ok 1 number(s): "835642397"

Test #20:

score: 0
Accepted
time: 8ms
memory: 8248kb

input:

-37 -124 151
867
76

output:

225290884 

result:

ok 1 number(s): "225290884"

Test #21:

score: 0
Accepted
time: 13ms
memory: 8488kb

input:

-316 149 -149
1024
87

output:

374987754 

result:

ok 1 number(s): "374987754"

Test #22:

score: 0
Accepted
time: 14ms
memory: 8508kb

input:

370 545 81
1073
69

output:

943329809 

result:

ok 1 number(s): "943329809"

Test #23:

score: 0
Accepted
time: 23ms
memory: 8684kb

input:

-81 182 532
2048
87

output:

843173062 

result:

ok 1 number(s): "843173062"

Test #24:

score: 0
Accepted
time: 3ms
memory: 7676kb

input:

-1229 -1607 319
199
24

output:

1926 

result:

ok 1 number(s): "1926"

Test #25:

score: 0
Accepted
time: 58ms
memory: 9864kb

input:

43 -419 -613
4096
46

output:

418220629 

result:

ok 1 number(s): "418220629"

Test #26:

score: 0
Accepted
time: 31ms
memory: 9144kb

input:

3434 -3146 -1774
2601
46

output:

705802517 

result:

ok 1 number(s): "705802517"

Test #27:

score: 0
Accepted
time: 127ms
memory: 12204kb

input:

2193 -2331 2901
8192
75

output:

728593792 

result:

ok 1 number(s): "728593792"

Test #28:

score: 0
Accepted
time: 14ms
memory: 8252kb

input:

233 -4307 -4363
1093
81

output:

303899847 

result:

ok 1 number(s): "303899847"

Test #29:

score: 0
Accepted
time: 278ms
memory: 23300kb

input:

-4522 762 8059
16384
34

output:

190696426 

result:

ok 1 number(s): "190696426"

Test #30:

score: 0
Accepted
time: 329ms
memory: 21816kb

input:

-5155 -3639 15798
24822
55

output:

808461103 

result:

ok 1 number(s): "808461103"

Test #31:

score: 0
Accepted
time: 607ms
memory: 29768kb

input:

15234 4368 12248
32768
19

output:

115861480 

result:

ok 1 number(s): "115861480"

Test #32:

score: 0
Accepted
time: 683ms
memory: 34024kb

input:

820 30492 3951
42789
76

output:

826647308 

result:

ok 1 number(s): "826647308"

Test #33:

score: 0
Accepted
time: 1343ms
memory: 57040kb

input:

1372 -24835 -24597
65536
65

output:

355997764 

result:

ok 1 number(s): "355997764"

Test #34:

score: 0
Accepted
time: 1491ms
memory: 66588kb

input:

-59726 17559 -45875
87143
58

output:

326130350 

result:

ok 1 number(s): "326130350"

Test #35:

score: 0
Accepted
time: 2942ms
memory: 114700kb

input:

-27584 51950 23030
131072
74

output:

325794325 

result:

ok 1 number(s): "325794325"

Test #36:

score: 0
Accepted
time: 3237ms
memory: 125672kb

input:

61155 52006 74974
164861
5

output:

160748350 

result:

ok 1 number(s): "160748350"

Test #37:

score: 0
Accepted
time: 3365ms
memory: 135104kb

input:

41344 -81596 -95774
200000
59

output:

965482998 

result:

ok 1 number(s): "965482998"

Test #38:

score: 0
Accepted
time: 320ms
memory: 20044kb

input:

42056 -90767 -54649
24350
63

output:

132823 

result:

ok 1 number(s): "132823"

Test #39:

score: 0
Accepted
time: 3400ms
memory: 134576kb

input:

-74335 43393 57021
199994
67

output:

310210583 

result:

ok 1 number(s): "310210583"

Test #40:

score: 0
Accepted
time: 3097ms
memory: 121808kb

input:

-80838 73772 -18618
134415
57

output:

346157175 

result:

ok 1 number(s): "346157175"

Test #41:

score: 0
Accepted
time: 3379ms
memory: 135028kb

input:

37457 74497 -81166
199997
59

output:

26667908 

result:

ok 1 number(s): "26667908"

Test #42:

score: 0
Accepted
time: 3219ms
memory: 124556kb

input:

31109 -65140 -77085
162412
46

output:

12858959 

result:

ok 1 number(s): "12858959"

Test #43:

score: 0
Accepted
time: 3382ms
memory: 133524kb

input:

-58550 -97769 66373
199995
86

output:

789346262 

result:

ok 1 number(s): "789346262"

Test #44:

score: 0
Accepted
time: 1750ms
memory: 76080kb

input:

7739 58831 72332
124270
16

output:

167162440 

result:

ok 1 number(s): "167162440"

Test #45:

score: 0
Accepted
time: 3390ms
memory: 134608kb

input:

-97901 25173 -99145
199999
52

output:

797290311 

result:

ok 1 number(s): "797290311"

Test #46:

score: 0
Accepted
time: 1771ms
memory: 79820kb

input:

-87118 -60882 -86669
126103
23

output:

487838027 

result:

ok 1 number(s): "487838027"

Test #47:

score: 0
Accepted
time: 3392ms
memory: 133244kb

input:

-71646 69885 70206
200000
27

output:

285981891 

result:

ok 1 number(s): "285981891"

Test #48:

score: 0
Accepted
time: 1669ms
memory: 74644kb

input:

14475 -77173 -5177
117777
51

output:

251933976 

result:

ok 1 number(s): "251933976"

Test #49:

score: 0
Accepted
time: 3390ms
memory: 132004kb

input:

-35780 37165 54712
199996
14

output:

763964192 

result:

ok 1 number(s): "763964192"

Test #50:

score: 0
Accepted
time: 1567ms
memory: 68280kb

input:

15709 -72676 -22298
101968
17

output:

406652317 

result:

ok 1 number(s): "406652317"

Test #51:

score: 0
Accepted
time: 3358ms
memory: 134144kb

input:

74572 -98701 -56974
199991
62

output:

55467556 

result:

ok 1 number(s): "55467556"

Test #52:

score: 0
Accepted
time: 3273ms
memory: 125976kb

input:

-14644 -10031 -50353
168383
43

output:

376814948 

result:

ok 1 number(s): "376814948"

Test #53:

score: 0
Accepted
time: 3388ms
memory: 133620kb

input:

22388 51898 80903
199995
89

output:

832434478 

result:

ok 1 number(s): "832434478"

Test #54:

score: 0
Accepted
time: 1789ms
memory: 79596kb

input:

34062 -76211 -25545
127193
91

output:

234760702 

result:

ok 1 number(s): "234760702"

Test #55:

score: 0
Accepted
time: 3396ms
memory: 133368kb

input:

-19645 -45450 -16512
200000
77

output:

759439547 

result:

ok 1 number(s): "759439547"

Test #56:

score: 0
Accepted
time: 308ms
memory: 18988kb

input:

98957 80512 -24606
20311
30

output:

985804570 

result:

ok 1 number(s): "985804570"

Test #57:

score: 0
Accepted
time: 3409ms
memory: 134624kb

input:

-87259 -11505 14596
199994
83

output:

160520754 

result:

ok 1 number(s): "160520754"

Test #58:

score: 0
Accepted
time: 3425ms
memory: 134892kb

input:

0 0 0
200000
0

output:

393458944 

result:

ok 1 number(s): "393458944"

Test #59:

score: 0
Accepted
time: 3424ms
memory: 134584kb

input:

0 0 0
200000
100

output:

393458944 

result:

ok 1 number(s): "393458944"

Test #60:

score: 0
Accepted
time: 3412ms
memory: 135120kb

input:

-100000 -100000 -100000
200000
75

output:

393458944 

result:

ok 1 number(s): "393458944"

Test #61:

score: 0
Accepted
time: 3418ms
memory: 133184kb

input:

100000 100000 100000
200000
63

output:

393458944 

result:

ok 1 number(s): "393458944"

Test #62:

score: 0
Accepted
time: 3391ms
memory: 134092kb

input:

100000 0 -100000
200000
56

output:

678255914 

result:

ok 1 number(s): "678255914"

Test #63:

score: 0
Accepted
time: 3425ms
memory: 133544kb

input:

0 1 2
200000
22

output:

630634769 

result:

ok 1 number(s): "630634769"

Test #64:

score: 0
Accepted
time: 2ms
memory: 7664kb

input:

100000 0 -100000
1
32

output:

200000 

result:

ok 1 number(s): "200000"

Test #65:

score: 0
Accepted
time: 1ms
memory: 7756kb

input:

100000 100000 100000
1
33

output:

1 

result:

ok 1 number(s): "1"

Test #66:

score: 0
Accepted
time: 2ms
memory: 7884kb

input:

-100000 -100000 -100000
1
6

output:

1 

result:

ok 1 number(s): "1"

Test #67:

score: 0
Accepted
time: 1ms
memory: 7720kb

input:

100000 100000 -100000
1
7

output:

332948118 

result:

ok 1 number(s): "332948118"

Test #68:

score: 0
Accepted
time: 2ms
memory: 7724kb

input:

-100000 -100000 100000
1
40

output:

332948118 

result:

ok 1 number(s): "332948118"

Test #69:

score: 0
Accepted
time: 2ms
memory: 7748kb

input:

100000 -100000 -100000
100
63

output:

764105630 

result:

ok 1 number(s): "764105630"

Test #70:

score: 0
Accepted
time: 0ms
memory: 7684kb

input:

-100000 100000 100000
100
13

output:

764105630 

result:

ok 1 number(s): "764105630"

Test #71:

score: 0
Accepted
time: 0ms
memory: 7636kb

input:

-100000 100000 0
100
10

output:

200000 

result:

ok 1 number(s): "200000"

Test #72:

score: 0
Accepted
time: 1552ms
memory: 69072kb

input:

-100000 100000 0
99999
77

output:

200000 

result:

ok 1 number(s): "200000"

Test #73:

score: 0
Accepted
time: 1548ms
memory: 69704kb

input:

-100000 100000 0
100000
80

output:

200000 

result:

ok 1 number(s): "200000"

Test #74:

score: 0
Accepted
time: 1552ms
memory: 69152kb

input:

-100000 100000 0
100001
5

output:

50125708 

result:

ok 1 number(s): "50125708"