QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#118698#2618. Casual DancerszswzswzswAC ✓2412ms112012kbC++143.2kb2023-07-03 21:13:122023-07-03 21:13:15

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-07-03 21:13:15]
  • Judged
  • Verdict: AC
  • Time: 2412ms
  • Memory: 112012kb
  • [2023-07-03 21:13:12]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
const long long g0=3,g1=332748118;
const int N=8010000;
long long Pow(long long x,long long y){
	long long sum=1;
	for(;y;y>>=1,x=x*x%mod)if(y&1)sum=sum*x%mod;
	return sum;
}
namespace Poly
{
	int Pos,L,Rev[N];
	inline void Init(int ll){
		for(Pos=0,L=1;L<ll;L<<=1,++Pos);
		for(register int i=0;i<L;i++)Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Pos-1));
		return;
	}
	inline void NTT(long long *C,int opt)
	{
		for(register int i=0;i<L;i++)if(i<Rev[i])swap(C[i],C[Rev[i]]);
		for(register int mid=1;(mid<<1)<=L;mid<<=1){
			long long Wn=Pow((opt==0)?g0:g1,(mod-1)/(mid<<1)),W=1;
				for(register int i=0;i<L;i+=(mid<<1)){
					W=1;
					for(register int j=0;j<mid;j++,W=W*Wn%mod){
						long long tmp=C[i+mid+j]*W%mod;
						C[i+mid+j]=(C[i+j]+mod-tmp)%mod;
						C[i+j]=(C[i+j]+tmp)%mod;
					}
				}
			}if(opt==1){
			long long IV=Pow(L,mod-2);
			for(register int i=0;i<L;i++)C[i]=C[i]*IV%mod;
		}return;
	}

	inline void Dot(long long *A,long long *B,long long *C,int ll){
		for(register int i=0;i<ll;i++)C[i]=A[i]*B[i]%mod;return;
	}
	void Inte(long long *A,long long *B,int ll){
		for(int i=ll-1;i>=1;i--)B[i]=A[i-1]*Pow(i,mod-2)%mod;
		B[0]=0;return;
	}
	void Deri(long long *A,long long *B,int ll){
		for(int i=0;i<ll-1;i++)B[i]=A[i+1]*(i+1)%mod;
		B[ll-1]=0;return;
	}
	void Inv(long long *A,long long *B,int ll){
		static long long Tmp[N];for(int i=0;i<(ll<<2);i++)Tmp[i]=0;
		B[0]=Pow(A[0],mod-2);
		for(int now=2;now<(ll<<1);now<<=1){
			Init(now<<1);
			for(int i=0;i<now;i++)Tmp[i]=A[i];for(int i=now;i<(now<<1);i++)Tmp[i]=0;
			NTT(Tmp,0);NTT(B,0);
			for(int i=0;i<(now<<1);i++)B[i]=B[i]*(mod+2-Tmp[i]*B[i]%mod)%mod;
			NTT(B,1);
			for(int i=now;i<(now<<1);i++)B[i]=0;
		}for(int i=ll;i<L;i++)B[i]=0;return;
	}
	void Ln(long long *A,long long *B,int ll){
		static long long Tmp1[N],Tmp2[N];for(int i=0;i<(ll<<2);i++)Tmp1[i]=Tmp2[i]=0;
		Deri(A,Tmp1,ll);Inv(A,Tmp2,ll);
		Init(ll<<1);NTT(Tmp1,0);NTT(Tmp2,0);Dot(Tmp1,Tmp2,Tmp1,L);NTT(Tmp1,1);
		Inte(Tmp1,B,ll);return;
	}
	void Exp(long long *A,long long *B,int ll){
		static long long Tmp1[N],Tmp2[N];for(int i=0;i<(ll<<2);i++)Tmp1[i]=Tmp2[i]=0;
		B[0]=1;
		for(int now=2;now<(ll<<1);now<<=1)
		{
			Ln(B,Tmp1,now);for(int i=now;i<(now<<1);i++)Tmp1[i]=0;
			for(int i=0;i<now;i++)Tmp2[i]=A[i];for(int i=now;i<(now<<1);i++)Tmp2[i]=0;
			Init(now<<1);
			NTT(Tmp1,0);NTT(Tmp2,0);NTT(B,0);
			for(int i=0;i<(now<<1);i++)B[i]=B[i]*(mod+1-Tmp1[i]+Tmp2[i])%mod;
			NTT(B,1);
			for(int i=now;i<(now<<1);i++)B[i]=0;
		}for(int i=ll;i<L;i++)B[i]=0;return;
	}
}
int n;
int A[4];
long long P1[N],P2[N],P3[N];
int main()
{
	for(int i=1;i<=3;i++)cin>>A[i];
	cin>>n;
	P1[0]=Pow(10,mod-2);P1[2]=P1[1]=P1[0];
	Poly::Ln(P1,P2,n*2+1);
	for(int i=0;i<=n*2;i++)P2[i]=P2[i]*n%mod;
	Poly::Exp(P2,P3,n*2+1);
	long long t=Pow(Pow(3,n),mod-2);
	for(int i=0;i<=n*2;i++)P3[i]=P3[i]*t%mod;
	long long res=0;
	for(int i=1;i<=2;i++)
		for(int j=i+1,L;j<=3;j++){
			L=abs(A[i]-A[j]);
			for(int k=0;k<=n*2;k++){
				res+=P3[k]*abs(L+n-k)%mod;
				res%=mod;
			}
		}
	res=res*Pow(2,mod-2)%mod;
	cout<<res;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 19784kb

input:

0 0 0
1
58

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

1 2 2
1
100

output:

332748119

result:

ok 1 number(s): "332748119"

Test #3:

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

input:

5 2 3
4
50

output:

160212060

result:

ok 1 number(s): "160212060"

Test #4:

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

input:

-2 -1 1
2
71

output:

443664160

result:

ok 1 number(s): "443664160"

Test #5:

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

input:

-1 0 -1
4
8

output:

751764268

result:

ok 1 number(s): "751764268"

Test #6:

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

input:

-2 -2 2
5
54

output:

801060288

result:

ok 1 number(s): "801060288"

Test #7:

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

input:

-2 2 4
8
36

output:

353135983

result:

ok 1 number(s): "353135983"

Test #8:

score: 0
Accepted
time: 4ms
memory: 19952kb

input:

8 -7 1
7
28

output:

15

result:

ok 1 number(s): "15"

Test #9:

score: 0
Accepted
time: 4ms
memory: 19788kb

input:

-7 -8 0
16
54

output:

159363041

result:

ok 1 number(s): "159363041"

Test #10:

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

input:

5 11 -11
9
32

output:

717226646

result:

ok 1 number(s): "717226646"

Test #11:

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

input:

-16 1 -9
32
8

output:

855967855

result:

ok 1 number(s): "855967855"

Test #12:

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

input:

-13 28 28
37
80

output:

116405794

result:

ok 1 number(s): "116405794"

Test #13:

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

input:

6 26 -25
64
21

output:

91053409

result:

ok 1 number(s): "91053409"

Test #14:

score: 0
Accepted
time: 4ms
memory: 19852kb

input:

-39 23 1
31
64

output:

742331784

result:

ok 1 number(s): "742331784"

Test #15:

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

input:

-32 42 43
128
87

output:

57822539

result:

ok 1 number(s): "57822539"

Test #16:

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

input:

-80 55 -106
142
29

output:

435655440

result:

ok 1 number(s): "435655440"

Test #17:

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

input:

0 -83 -106
256
55

output:

120508896

result:

ok 1 number(s): "120508896"

Test #18:

score: 0
Accepted
time: 4ms
memory: 19792kb

input:

-100 -123 -167
91
74

output:

285780715

result:

ok 1 number(s): "285780715"

Test #19:

score: 0
Accepted
time: 9ms
memory: 19812kb

input:

252 -176 -239
512
49

output:

835642397

result:

ok 1 number(s): "835642397"

Test #20:

score: 0
Accepted
time: 4ms
memory: 19812kb

input:

-37 -124 151
867
76

output:

225290884

result:

ok 1 number(s): "225290884"

Test #21:

score: 0
Accepted
time: 10ms
memory: 19916kb

input:

-316 149 -149
1024
87

output:

374987754

result:

ok 1 number(s): "374987754"

Test #22:

score: 0
Accepted
time: 9ms
memory: 19856kb

input:

370 545 81
1073
69

output:

943329809

result:

ok 1 number(s): "943329809"

Test #23:

score: 0
Accepted
time: 21ms
memory: 19980kb

input:

-81 182 532
2048
87

output:

843173062

result:

ok 1 number(s): "843173062"

Test #24:

score: 0
Accepted
time: 5ms
memory: 19788kb

input:

-1229 -1607 319
199
24

output:

1926

result:

ok 1 number(s): "1926"

Test #25:

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

input:

43 -419 -613
4096
46

output:

418220629

result:

ok 1 number(s): "418220629"

Test #26:

score: 0
Accepted
time: 21ms
memory: 19892kb

input:

3434 -3146 -1774
2601
46

output:

705802517

result:

ok 1 number(s): "705802517"

Test #27:

score: 0
Accepted
time: 105ms
memory: 24400kb

input:

2193 -2331 2901
8192
75

output:

728593792

result:

ok 1 number(s): "728593792"

Test #28:

score: 0
Accepted
time: 4ms
memory: 22032kb

input:

233 -4307 -4363
1093
81

output:

303899847

result:

ok 1 number(s): "303899847"

Test #29:

score: 0
Accepted
time: 210ms
memory: 31044kb

input:

-4522 762 8059
16384
34

output:

190696426

result:

ok 1 number(s): "190696426"

Test #30:

score: 0
Accepted
time: 212ms
memory: 31024kb

input:

-5155 -3639 15798
24822
55

output:

808461103

result:

ok 1 number(s): "808461103"

Test #31:

score: 0
Accepted
time: 467ms
memory: 38188kb

input:

15234 4368 12248
32768
19

output:

115861480

result:

ok 1 number(s): "115861480"

Test #32:

score: 0
Accepted
time: 476ms
memory: 40256kb

input:

820 30492 3951
42789
76

output:

826647308

result:

ok 1 number(s): "826647308"

Test #33:

score: 0
Accepted
time: 1072ms
memory: 58768kb

input:

1372 -24835 -24597
65536
65

output:

355997764

result:

ok 1 number(s): "355997764"

Test #34:

score: 0
Accepted
time: 1065ms
memory: 62800kb

input:

-59726 17559 -45875
87143
58

output:

326130350

result:

ok 1 number(s): "326130350"

Test #35:

score: 0
Accepted
time: 2392ms
memory: 99652kb

input:

-27584 51950 23030
131072
74

output:

325794325

result:

ok 1 number(s): "325794325"

Test #36:

score: 0
Accepted
time: 2355ms
memory: 103748kb

input:

61155 52006 74974
164861
5

output:

160748350

result:

ok 1 number(s): "160748350"

Test #37:

score: 0
Accepted
time: 2377ms
memory: 109904kb

input:

41344 -81596 -95774
200000
59

output:

965482998

result:

ok 1 number(s): "965482998"

Test #38:

score: 0
Accepted
time: 217ms
memory: 33088kb

input:

42056 -90767 -54649
24350
63

output:

132823

result:

ok 1 number(s): "132823"

Test #39:

score: 0
Accepted
time: 2390ms
memory: 111936kb

input:

-74335 43393 57021
199994
67

output:

310210583

result:

ok 1 number(s): "310210583"

Test #40:

score: 0
Accepted
time: 2344ms
memory: 99656kb

input:

-80838 73772 -18618
134415
57

output:

346157175

result:

ok 1 number(s): "346157175"

Test #41:

score: 0
Accepted
time: 2401ms
memory: 109896kb

input:

37457 74497 -81166
199997
59

output:

26667908

result:

ok 1 number(s): "26667908"

Test #42:

score: 0
Accepted
time: 2380ms
memory: 105816kb

input:

31109 -65140 -77085
162412
46

output:

12858959

result:

ok 1 number(s): "12858959"

Test #43:

score: 0
Accepted
time: 2355ms
memory: 107856kb

input:

-58550 -97769 66373
199995
86

output:

789346262

result:

ok 1 number(s): "789346262"

Test #44:

score: 0
Accepted
time: 1064ms
memory: 66836kb

input:

7739 58831 72332
124270
16

output:

167162440

result:

ok 1 number(s): "167162440"

Test #45:

score: 0
Accepted
time: 2398ms
memory: 109836kb

input:

-97901 25173 -99145
199999
52

output:

797290311

result:

ok 1 number(s): "797290311"

Test #46:

score: 0
Accepted
time: 1070ms
memory: 66896kb

input:

-87118 -60882 -86669
126103
23

output:

487838027

result:

ok 1 number(s): "487838027"

Test #47:

score: 0
Accepted
time: 2367ms
memory: 109892kb

input:

-71646 69885 70206
200000
27

output:

285981891

result:

ok 1 number(s): "285981891"

Test #48:

score: 0
Accepted
time: 1049ms
memory: 69068kb

input:

14475 -77173 -5177
117777
51

output:

251933976

result:

ok 1 number(s): "251933976"

Test #49:

score: 0
Accepted
time: 2376ms
memory: 110024kb

input:

-35780 37165 54712
199996
14

output:

763964192

result:

ok 1 number(s): "763964192"

Test #50:

score: 0
Accepted
time: 1068ms
memory: 64812kb

input:

15709 -72676 -22298
101968
17

output:

406652317

result:

ok 1 number(s): "406652317"

Test #51:

score: 0
Accepted
time: 2391ms
memory: 107956kb

input:

74572 -98701 -56974
199991
62

output:

55467556

result:

ok 1 number(s): "55467556"

Test #52:

score: 0
Accepted
time: 2367ms
memory: 105804kb

input:

-14644 -10031 -50353
168383
43

output:

376814948

result:

ok 1 number(s): "376814948"

Test #53:

score: 0
Accepted
time: 2381ms
memory: 109888kb

input:

22388 51898 80903
199995
89

output:

832434478

result:

ok 1 number(s): "832434478"

Test #54:

score: 0
Accepted
time: 1080ms
memory: 68940kb

input:

34062 -76211 -25545
127193
91

output:

234760702

result:

ok 1 number(s): "234760702"

Test #55:

score: 0
Accepted
time: 2387ms
memory: 109880kb

input:

-19645 -45450 -16512
200000
77

output:

759439547

result:

ok 1 number(s): "759439547"

Test #56:

score: 0
Accepted
time: 215ms
memory: 28948kb

input:

98957 80512 -24606
20311
30

output:

985804570

result:

ok 1 number(s): "985804570"

Test #57:

score: 0
Accepted
time: 2367ms
memory: 107852kb

input:

-87259 -11505 14596
199994
83

output:

160520754

result:

ok 1 number(s): "160520754"

Test #58:

score: 0
Accepted
time: 2373ms
memory: 112012kb

input:

0 0 0
200000
0

output:

393458944

result:

ok 1 number(s): "393458944"

Test #59:

score: 0
Accepted
time: 2384ms
memory: 107840kb

input:

0 0 0
200000
100

output:

393458944

result:

ok 1 number(s): "393458944"

Test #60:

score: 0
Accepted
time: 2396ms
memory: 108008kb

input:

-100000 -100000 -100000
200000
75

output:

393458944

result:

ok 1 number(s): "393458944"

Test #61:

score: 0
Accepted
time: 2377ms
memory: 109964kb

input:

100000 100000 100000
200000
63

output:

393458944

result:

ok 1 number(s): "393458944"

Test #62:

score: 0
Accepted
time: 2401ms
memory: 107840kb

input:

100000 0 -100000
200000
56

output:

678255914

result:

ok 1 number(s): "678255914"

Test #63:

score: 0
Accepted
time: 2412ms
memory: 109772kb

input:

0 1 2
200000
22

output:

630634769

result:

ok 1 number(s): "630634769"

Test #64:

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

input:

100000 0 -100000
1
32

output:

200000

result:

ok 1 number(s): "200000"

Test #65:

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

input:

100000 100000 100000
1
33

output:

1

result:

ok 1 number(s): "1"

Test #66:

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

input:

-100000 -100000 -100000
1
6

output:

1

result:

ok 1 number(s): "1"

Test #67:

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

input:

100000 100000 -100000
1
7

output:

332948118

result:

ok 1 number(s): "332948118"

Test #68:

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

input:

-100000 -100000 100000
1
40

output:

332948118

result:

ok 1 number(s): "332948118"

Test #69:

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

input:

100000 -100000 -100000
100
63

output:

764105630

result:

ok 1 number(s): "764105630"

Test #70:

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

input:

-100000 100000 100000
100
13

output:

764105630

result:

ok 1 number(s): "764105630"

Test #71:

score: 0
Accepted
time: 4ms
memory: 19764kb

input:

-100000 100000 0
100
10

output:

200000

result:

ok 1 number(s): "200000"

Test #72:

score: 0
Accepted
time: 1071ms
memory: 64836kb

input:

-100000 100000 0
99999
77

output:

200000

result:

ok 1 number(s): "200000"

Test #73:

score: 0
Accepted
time: 1066ms
memory: 62860kb

input:

-100000 100000 0
100000
80

output:

200000

result:

ok 1 number(s): "200000"

Test #74:

score: 0
Accepted
time: 1065ms
memory: 64848kb

input:

-100000 100000 0
100001
5

output:

50125708

result:

ok 1 number(s): "50125708"