QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#49615#2618. Casual DancersCrysflyAC ✓1233ms46460kbC++116.3kb2022-09-22 08:57:012022-09-22 08:57:03

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.
  • [2022-09-22 08:57:03]
  • Judged
  • Verdict: AC
  • Time: 1233ms
  • Memory: 46460kb
  • [2022-09-22 08:57:01]
  • Submitted

answer

#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
//#define int long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

// modint
#define mod 998244353
struct modint{
	int x;
	modint(int o=0){x=o;}
	modint &operator = (int o){return x=o,*this;}
	modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
	modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
	modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
	modint &operator ^=(int b){
		modint a=*this,c=1;
		for(;b;b>>=1,a*=a)if(b&1)c*=a;
		return x=c.x,*this;
	}
	modint &operator /=(modint o){return *this *=o^=mod-2;}
	modint &operator +=(int o){return x=x+o>=mod?x+o-mod:x+o,*this;}
	modint &operator -=(int o){return x=x-o<0?x-o+mod:x-o,*this;}
	modint &operator *=(int o){return x=1ll*x*o%mod,*this;}
	modint &operator /=(int o){return *this *= ((modint(o))^=mod-2);}
	template<class I>friend modint operator +(modint a,I b){return a+=b;}
	template<class I>friend modint operator -(modint a,I b){return a-=b;}
	template<class I>friend modint operator *(modint a,I b){return a*=b;}
	template<class I>friend modint operator /(modint a,I b){return a/=b;}
	friend modint operator ^(modint a,int b){return a^=b;}
	friend bool operator ==(modint a,int b){return a.x==b;}
	friend bool operator !=(modint a,int b){return a.x!=b;}
	bool operator ! () {return !x;}
	modint operator - () {return x?mod-x:0;}
	bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}

vector<modint> fac,ifac,iv;
inline void initC(int n)
{
	if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
	int m=iv.size(); ++n;
	if(m>=n)return;
	iv.resize(n),fac.resize(n),ifac.resize(n);
	For(i,m,n-1){
		iv[i]=iv[mod%i]*(mod-mod/i);
		fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
	}
}
inline modint C(int n,int m){
	if(m<0||n<m)return 0;
	return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define poly vector<modint>
const modint G=3,Ginv=modint(1)/3;
inline poly one(){poly a;a.push_back(1);return a;}
vector<int>rev;
vector<modint>rts;
inline int ext(int n){
	int k=0;
	while((1<<k)<n)++k;return k; 
}
inline void init(int k){
	int n=1<<k;
	if(rev.size()==n)return;
	rev.resize(n);
	For(i,0,n-1)rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
	if(rts.size()>=n)return;
	int lst=max(1,(int)rts.size()); rts.resize(n);
	for(int mid=lst;mid<n;mid<<=1){
		modint wn=G^((mod-1)/(mid<<1));
		rts[mid]=1;
		For(i,1,mid-1)rts[i+mid]=rts[i+mid-1]*wn;
	}
}
void ntt(poly&a,int k,int typ)
{
	int n=1<<k;
	if(typ<0) reverse(a.begin()+1,a.end());
	For(i,0,n-1)if(i<rev[i])swap(a[i],a[rev[i]]); 
	for(int mid=1;mid<n;mid<<=1)
		for(int r=mid<<1,j=0;j<n;j+=r)
			for(int k=0;k<mid;++k){
				modint x=a[j+k],y=rts[mid+k]*a[j+k+mid];
				a[j+k]=x+y,a[j+k+mid]=x-y;
			}
	if(typ<0){
		modint inv=modint(1)/n;
		For(i,0,n-1)a[i]*=inv;
	}
}
 
poly operator +(poly a,poly b){
	int n=max(a.size(),b.size());a.resize(n),b.resize(n);
	For(i,0,n-1)a[i]+=b[i];return a;
}
poly operator -(poly a,poly b){
	int n=max(a.size(),b.size());a.resize(n),b.resize(n);
	For(i,0,n-1)a[i]-=b[i];return a;
}
poly operator *(poly a,modint b){
	int n=a.size();
	For(i,0,n-1)a[i]*=b;return a;
} 
poly operator *(poly a,poly b)
{
	if((int)a.size()<=64 && (int)b.size()<=64){
		poly c(a.size()+b.size()-1,0);
		for(int i=0;i<a.size();++i)
			for(int j=0;j<b.size();++j)
				c[i+j]+=a[i]*b[j];
		return c; 
	}
	int n=(int)a.size()+(int)b.size()-1,k=ext(n);
	a.resize(1<<k),b.resize(1<<k),init(k);
	ntt(a,k,1),ntt(b,k,1);
	For(i,0,(1<<k)-1)a[i]*=b[i];
	ntt(a,k,-1),a.resize(n);return a;
}

poly Tmp;
poly pmul(poly a,poly b,int n,bool ok=0)
{
	int k=ext(n); init(k);
	a.resize(1<<k),ntt(a,k,1);
	if(!ok) b.resize(1<<k),ntt(b,k,1),Tmp=b;
	For(i,0,(1<<k)-1)a[i]*=Tmp[i];
	ntt(a,k,-1),a.resize(n);
	return a;
}
poly inv(poly a,int n)
{
	a.resize(n);
	if(n==1){
		poly f(1,1/a[0]);
		return f;
	}
	poly f0=inv(a,(n+1)>>1),f=f0;
	poly now=pmul(a,f0,n,0);
	for(int i=0;i<f0.size();++i)now[i]=0;
	now=pmul(now,poly(0),n,1);
	f.resize(n);
	for(int i=f0.size();i<n;++i)f[i]=-now[i];
	return f;
}
poly inv(poly a){
	return inv(a,a.size());
}

poly deriv(poly a){
	int n=(int)a.size()-1;
	For(i,0,n-1)a[i]=a[i+1]*(i+1);
	a.resize(n);return a;
}
poly inter(poly a){
	int n=a.size()+1;a.resize(n);
	Rep(i,n-1,1)a[i]=a[i-1]/i;
	a[0]=0;return a;
}
poly ln(poly a){
	int n=a.size();
	a=inter(deriv(a)*inv(a));
	a.resize(n);return a;
}
poly exp(poly a,int k){
	int n=1<<k;a.resize(n);
	if(n==1)return one();
	poly f0=exp(a,k-1);f0.resize(n);
	return f0*(one()+a-ln(f0)); 
}
poly exp(poly a){
	int n=a.size();
	a=exp(a,ext(n));a.resize(n);return a;
}
poly div(poly a,poly b){
	int n=a.size(),m=b.size(),k=ext(n-m+1);
	reverse(a.begin(),a.end()),reverse(b.begin(),b.end());
	a.resize(n-m+1),b.resize(n-m+1);
	a=a*inv(b),a.resize(n-m+1),reverse(a.begin(),a.end()); return a;
}
poly modulo(poly a,poly b){
	if(b.size()>a.size())return a;
	int n=b.size()-1;
	a=a-div(a,b)*b;a.resize(n);return a;
}

#define maxn 1000005
#define inf 0x3f3f3f3f

int x[4],k;
modint p;
modint mul;

poly f,g;

modint calc(int x){
	modint res=0;
	For(i,-k,k){
		int d=x+i;
		d=abs(d);
		res+=g[i+k]*d;
	}
	res*=mul;
	return res;
}

signed main()
{
	For(i,1,3)x[i]=read();
	k=read();
	p=read(),p/=100;
	initC(k);
	mul=3; mul^=k; mul=1/mul;
//	f.resize(k+1),g.resize(k+1);
//	For(i,0,k) f[i]=ifac[i],g[i]=ifac[k-i];
//	f=f*g;
	
//	f.resize(2*k+1);
//	For(i,0,k)
//		For(j,0,k-i)
//			f[k-i+j] += ifac[j]*ifac[i]*ifac[k-i-j];
	g.resize(2*k+1);
	For(i,0,2)g[i]=1;
	g=exp(ln(g)*k);
	
//	For(i,0,k*2)cout<<(f[i]*fac[k]).x<<' ';puts("");
//	For(i,0,k*2)cout<<(g[i]).x<<" ";puts("");
//	For(i,1,k*2)cout<<((f[i]-f[i-1])*fac[k]).x<<" ";puts("");
	modint res=0;
	For(i,1,2)For(j,i+1,3)res+=calc(x[i]-x[j]);
	res/=2;
	cout<<res.x;
	return 0;
}
/*
sqrt(2*3),sqrt(3*5)
can get:sqrt(2*5)

5 2 3
10
50

*/

详细

Test #1:

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

input:

0 0 0
1
58

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

1 2 2
1
100

output:

332748119

result:

ok 1 number(s): "332748119"

Test #3:

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

input:

5 2 3
4
50

output:

160212060

result:

ok 1 number(s): "160212060"

Test #4:

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

input:

-2 -1 1
2
71

output:

443664160

result:

ok 1 number(s): "443664160"

Test #5:

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

input:

-1 0 -1
4
8

output:

751764268

result:

ok 1 number(s): "751764268"

Test #6:

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

input:

-2 -2 2
5
54

output:

801060288

result:

ok 1 number(s): "801060288"

Test #7:

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

input:

-2 2 4
8
36

output:

353135983

result:

ok 1 number(s): "353135983"

Test #8:

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

input:

8 -7 1
7
28

output:

15

result:

ok 1 number(s): "15"

Test #9:

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

input:

-7 -8 0
16
54

output:

159363041

result:

ok 1 number(s): "159363041"

Test #10:

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

input:

5 11 -11
9
32

output:

717226646

result:

ok 1 number(s): "717226646"

Test #11:

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

input:

-16 1 -9
32
8

output:

855967855

result:

ok 1 number(s): "855967855"

Test #12:

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

input:

-13 28 28
37
80

output:

116405794

result:

ok 1 number(s): "116405794"

Test #13:

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

input:

6 26 -25
64
21

output:

91053409

result:

ok 1 number(s): "91053409"

Test #14:

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

input:

-39 23 1
31
64

output:

742331784

result:

ok 1 number(s): "742331784"

Test #15:

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

input:

-32 42 43
128
87

output:

57822539

result:

ok 1 number(s): "57822539"

Test #16:

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

input:

-80 55 -106
142
29

output:

435655440

result:

ok 1 number(s): "435655440"

Test #17:

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

input:

0 -83 -106
256
55

output:

120508896

result:

ok 1 number(s): "120508896"

Test #18:

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

input:

-100 -123 -167
91
74

output:

285780715

result:

ok 1 number(s): "285780715"

Test #19:

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

input:

252 -176 -239
512
49

output:

835642397

result:

ok 1 number(s): "835642397"

Test #20:

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

input:

-37 -124 151
867
76

output:

225290884

result:

ok 1 number(s): "225290884"

Test #21:

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

input:

-316 149 -149
1024
87

output:

374987754

result:

ok 1 number(s): "374987754"

Test #22:

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

input:

370 545 81
1073
69

output:

943329809

result:

ok 1 number(s): "943329809"

Test #23:

score: 0
Accepted
time: 15ms
memory: 3936kb

input:

-81 182 532
2048
87

output:

843173062

result:

ok 1 number(s): "843173062"

Test #24:

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

input:

-1229 -1607 319
199
24

output:

1926

result:

ok 1 number(s): "1926"

Test #25:

score: 0
Accepted
time: 25ms
memory: 4520kb

input:

43 -419 -613
4096
46

output:

418220629

result:

ok 1 number(s): "418220629"

Test #26:

score: 0
Accepted
time: 16ms
memory: 4008kb

input:

3434 -3146 -1774
2601
46

output:

705802517

result:

ok 1 number(s): "705802517"

Test #27:

score: 0
Accepted
time: 57ms
memory: 5816kb

input:

2193 -2331 2901
8192
75

output:

728593792

result:

ok 1 number(s): "728593792"

Test #28:

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

input:

233 -4307 -4363
1093
81

output:

303899847

result:

ok 1 number(s): "303899847"

Test #29:

score: 0
Accepted
time: 108ms
memory: 7844kb

input:

-4522 762 8059
16384
34

output:

190696426

result:

ok 1 number(s): "190696426"

Test #30:

score: 0
Accepted
time: 129ms
memory: 8592kb

input:

-5155 -3639 15798
24822
55

output:

808461103

result:

ok 1 number(s): "808461103"

Test #31:

score: 0
Accepted
time: 244ms
memory: 13500kb

input:

15234 4368 12248
32768
19

output:

115861480

result:

ok 1 number(s): "115861480"

Test #32:

score: 0
Accepted
time: 241ms
memory: 14104kb

input:

820 30492 3951
42789
76

output:

826647308

result:

ok 1 number(s): "826647308"

Test #33:

score: 0
Accepted
time: 493ms
memory: 23652kb

input:

1372 -24835 -24597
65536
65

output:

355997764

result:

ok 1 number(s): "355997764"

Test #34:

score: 0
Accepted
time: 530ms
memory: 25368kb

input:

-59726 17559 -45875
87143
58

output:

326130350

result:

ok 1 number(s): "326130350"

Test #35:

score: 0
Accepted
time: 1106ms
memory: 43680kb

input:

-27584 51950 23030
131072
74

output:

325794325

result:

ok 1 number(s): "325794325"

Test #36:

score: 0
Accepted
time: 1122ms
memory: 45716kb

input:

61155 52006 74974
164861
5

output:

160748350

result:

ok 1 number(s): "160748350"

Test #37:

score: 0
Accepted
time: 1233ms
memory: 46332kb

input:

41344 -81596 -95774
200000
59

output:

965482998

result:

ok 1 number(s): "965482998"

Test #38:

score: 0
Accepted
time: 129ms
memory: 8736kb

input:

42056 -90767 -54649
24350
63

output:

132823

result:

ok 1 number(s): "132823"

Test #39:

score: 0
Accepted
time: 1108ms
memory: 46372kb

input:

-74335 43393 57021
199994
67

output:

310210583

result:

ok 1 number(s): "310210583"

Test #40:

score: 0
Accepted
time: 1098ms
memory: 43612kb

input:

-80838 73772 -18618
134415
57

output:

346157175

result:

ok 1 number(s): "346157175"

Test #41:

score: 0
Accepted
time: 1148ms
memory: 46380kb

input:

37457 74497 -81166
199997
59

output:

26667908

result:

ok 1 number(s): "26667908"

Test #42:

score: 0
Accepted
time: 1113ms
memory: 43784kb

input:

31109 -65140 -77085
162412
46

output:

12858959

result:

ok 1 number(s): "12858959"

Test #43:

score: 0
Accepted
time: 1145ms
memory: 46392kb

input:

-58550 -97769 66373
199995
86

output:

789346262

result:

ok 1 number(s): "789346262"

Test #44:

score: 0
Accepted
time: 556ms
memory: 24712kb

input:

7739 58831 72332
124270
16

output:

167162440

result:

ok 1 number(s): "167162440"

Test #45:

score: 0
Accepted
time: 1144ms
memory: 46372kb

input:

-97901 25173 -99145
199999
52

output:

797290311

result:

ok 1 number(s): "797290311"

Test #46:

score: 0
Accepted
time: 542ms
memory: 24792kb

input:

-87118 -60882 -86669
126103
23

output:

487838027

result:

ok 1 number(s): "487838027"

Test #47:

score: 0
Accepted
time: 1220ms
memory: 46372kb

input:

-71646 69885 70206
200000
27

output:

285981891

result:

ok 1 number(s): "285981891"

Test #48:

score: 0
Accepted
time: 559ms
memory: 25912kb

input:

14475 -77173 -5177
117777
51

output:

251933976

result:

ok 1 number(s): "251933976"

Test #49:

score: 0
Accepted
time: 1088ms
memory: 46308kb

input:

-35780 37165 54712
199996
14

output:

763964192

result:

ok 1 number(s): "763964192"

Test #50:

score: 0
Accepted
time: 597ms
memory: 24972kb

input:

15709 -72676 -22298
101968
17

output:

406652317

result:

ok 1 number(s): "406652317"

Test #51:

score: 0
Accepted
time: 1134ms
memory: 46332kb

input:

74572 -98701 -56974
199991
62

output:

55467556

result:

ok 1 number(s): "55467556"

Test #52:

score: 0
Accepted
time: 1102ms
memory: 44492kb

input:

-14644 -10031 -50353
168383
43

output:

376814948

result:

ok 1 number(s): "376814948"

Test #53:

score: 0
Accepted
time: 1160ms
memory: 46404kb

input:

22388 51898 80903
199995
89

output:

832434478

result:

ok 1 number(s): "832434478"

Test #54:

score: 0
Accepted
time: 563ms
memory: 24608kb

input:

34062 -76211 -25545
127193
91

output:

234760702

result:

ok 1 number(s): "234760702"

Test #55:

score: 0
Accepted
time: 1125ms
memory: 46368kb

input:

-19645 -45450 -16512
200000
77

output:

759439547

result:

ok 1 number(s): "759439547"

Test #56:

score: 0
Accepted
time: 131ms
memory: 8380kb

input:

98957 80512 -24606
20311
30

output:

985804570

result:

ok 1 number(s): "985804570"

Test #57:

score: 0
Accepted
time: 1128ms
memory: 46460kb

input:

-87259 -11505 14596
199994
83

output:

160520754

result:

ok 1 number(s): "160520754"

Test #58:

score: 0
Accepted
time: 1116ms
memory: 46368kb

input:

0 0 0
200000
0

output:

393458944

result:

ok 1 number(s): "393458944"

Test #59:

score: 0
Accepted
time: 1173ms
memory: 46284kb

input:

0 0 0
200000
100

output:

393458944

result:

ok 1 number(s): "393458944"

Test #60:

score: 0
Accepted
time: 1121ms
memory: 46284kb

input:

-100000 -100000 -100000
200000
75

output:

393458944

result:

ok 1 number(s): "393458944"

Test #61:

score: 0
Accepted
time: 1142ms
memory: 46372kb

input:

100000 100000 100000
200000
63

output:

393458944

result:

ok 1 number(s): "393458944"

Test #62:

score: 0
Accepted
time: 1114ms
memory: 46452kb

input:

100000 0 -100000
200000
56

output:

678255914

result:

ok 1 number(s): "678255914"

Test #63:

score: 0
Accepted
time: 1161ms
memory: 46368kb

input:

0 1 2
200000
22

output:

630634769

result:

ok 1 number(s): "630634769"

Test #64:

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

input:

100000 0 -100000
1
32

output:

200000

result:

ok 1 number(s): "200000"

Test #65:

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

input:

100000 100000 100000
1
33

output:

1

result:

ok 1 number(s): "1"

Test #66:

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

input:

-100000 -100000 -100000
1
6

output:

1

result:

ok 1 number(s): "1"

Test #67:

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

input:

100000 100000 -100000
1
7

output:

332948118

result:

ok 1 number(s): "332948118"

Test #68:

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

input:

-100000 -100000 100000
1
40

output:

332948118

result:

ok 1 number(s): "332948118"

Test #69:

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

input:

100000 -100000 -100000
100
63

output:

764105630

result:

ok 1 number(s): "764105630"

Test #70:

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

input:

-100000 100000 100000
100
13

output:

764105630

result:

ok 1 number(s): "764105630"

Test #71:

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

input:

-100000 100000 0
100
10

output:

200000

result:

ok 1 number(s): "200000"

Test #72:

score: 0
Accepted
time: 542ms
memory: 24100kb

input:

-100000 100000 0
99999
77

output:

200000

result:

ok 1 number(s): "200000"

Test #73:

score: 0
Accepted
time: 564ms
memory: 24104kb

input:

-100000 100000 0
100000
80

output:

200000

result:

ok 1 number(s): "200000"

Test #74:

score: 0
Accepted
time: 554ms
memory: 24032kb

input:

-100000 100000 0
100001
5

output:

50125708

result:

ok 1 number(s): "50125708"