QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#118698 | #2618. Casual Dancers | zswzswzsw | AC ✓ | 2412ms | 112012kb | C++14 | 3.2kb | 2023-07-03 21:13:12 | 2023-07-03 21:13:15 |
Judging History
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"