QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#289336#6325. Peaceful ResultscccWA 1099ms167920kbC++143.2kb2023-12-23 17:03:222023-12-23 17:03:22

Judging History

你现在查看的是最新测评结果

  • [2023-12-23 17:03:22]
  • 评测
  • 测评结果:WA
  • 用时:1099ms
  • 内存:167920kb
  • [2023-12-23 17:03:22]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e6+56;
const int mod=998244353, G=3;
int ksm(int x,int y) { int ans=1; while(y) { if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1; } return ans; }
int Inv(int x) { return ksm(x,mod-2); }
const int invG=Inv(G);


int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
long double a[10][10]; int y[7];
void Read() { scanf("%lld",&n); really_n=n; scanf("%lld%lld%lld",&AR,&AP,&AS); scanf("%lld%lld%lld",&BR,&BP,&BS); scanf("%lld%lld%lld",&CR,&CP,&CS); }
void init() {
	a[1][1]=1.0; a[1][2]=1.0; a[1][3]=1.0; a[1][7]=AR-AS;
	a[2][4]=1.0; a[2][5]=1.0; a[2][6]=1.0; a[2][7]=AP-AS;
	a[3][1]=1.0; a[3][2]=-1.0; a[3][5]=1.0; a[3][6]=-1.0; a[3][7]=BR-BS;
	a[4][2]=-1.0; a[4][3]=1.0; a[4][4]=1.0; a[4][6]=-1.0; a[4][7]=BP-BS;
	a[5][1]=1.0; a[5][3]=-1.0; a[5][5]=-1.0; a[5][6]=1.0; a[5][7]=CR-CS;
	a[6][2]=1.0; a[6][3]=-1.0; a[6][4]=1.0; a[6][5]=-1.0; a[6][7]=CP-CS;
}
void solve_gs() {
	const long double eps=1e-8;
	int nukt=n; n=6;
	for(int i=1;i<=n;i++) {
		bool fbi=false;
		for(int j=i;j<=n;j++) { if(fabs(a[j][i])>eps) { fbi=true; for(int k=1;k<=n+1;k++) swap(a[i][k],a[j][k]); break; } }
		if(!fbi) { puts("0"); exit(0); }
		for(int j=1;j<=n;j++) {
			if(i==j) continue;
			long double num=a[j][i]/a[i][i];
			for(int k=i;k<=n+1;k++) a[j][k]-=a[i][k]*num;
		}
	}
	for(int i=1;i<=n;i++) {
		long double yi=a[i][n+1]/a[i][i];
//		printf("%.20Lf %.20Lf\n",yi,ceil(yi));
		if(yi+eps<=ceil(yi) and yi-eps>=floor(yi)) { puts("0"); exit(0); }
//		if(yi!=floor(yi)) { puts("0"); exit(0); }
		y[i]=yi;
	} puts("");
	n=nukt;
}
void solve1() {
	Read();
	init(); solve_gs();
//	for(int i=1;i<=6;i++) printf("%lld ",y[i]);
}


int tr[N];
void NTT(int *f,bool Is) {
	for(int i=0;i<n;i++) if(i<tr[i]) swap(f[i],f[tr[i]]);
	for(int p=2;p<=n;p<<=1) {
		int len=p>>1; int w_len_1=ksm( ( Is?G:invG ),(mod-1)/p );
		for(int str=0;str<n;str+=p) {
			int w_len_now=1;
			for(int i=str;i<str+len;i++) {
				int now=f[i+len]*w_len_now%mod;
				f[i+len]=( f[i]-now+mod )%mod;
				f[i]=( f[i]+now )%mod;
				w_len_now = w_len_now * w_len_1 % mod;
			}
		}
	}
}


int jc[N],inv[N];
int fa[N],fb[N],fc[N];
void INIT() {
	jc[0]=1; for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;
	inv[n]=ksm(jc[n],mod-2);
	for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
void solve2() {
	n=AS;//现在计算的是出S的步数
	int s1=max( 0ll,min(-y[1],-y[4]) ), s2=max( 0ll,min(-y[2],-y[5]) ), s3=max( 0ll,min(-y[3],-y[6]) );
	//每一项均为正整数,又因为y是差值,可得上式 
	int m=n; n=1; while(n<=2*m) n<<=1;
	
//	for(int i=1;i<=6;i++) cout<<y[i]<<" ";
	for(int i=s1;i<=m;i++) fa[i]=inv[i]*inv[i+y[1]]%mod*inv[i+y[4]]%mod;
	for(int i=s2;i<=m;i++) fb[i]=inv[i]*inv[i+y[2]]%mod*inv[i+y[5]]%mod;
	for(int i=s3;i<=m;i++) fc[i]=inv[i]*inv[i+y[3]]%mod*inv[i+y[6]]%mod;
	
	for(int i=0;i<n;i++) tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	
	NTT(fa,true); NTT(fb,true); NTT(fc,true);
	for(int i=0;i<n;i++) fa[i]=fa[i]*fb[i]%mod*fc[i]%mod;
	NTT(fa,false);
//	for(int i=0;i<n;i++) cout<<fa[i]<<" ";
	int ans=fa[m]*Inv(n)%mod*jc[really_n]%mod;
	printf("%lld",ans);
}


#undef int
int main() {
	solve1();
	INIT();
	solve2();
	return 0;
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
2 0 0
1 1 0
1 0 1

output:


2

result:

ok 1 number(s): "2"

Test #2:

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

input:

3
0 1 2
3 0 0
1 1 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 54ms
memory: 23744kb

input:

333333
111111 111111 111111
111111 111111 111111
111111 111111 111111

output:


383902959

result:

ok 1 number(s): "383902959"

Test #4:

score: 0
Accepted
time: 254ms
memory: 65748kb

input:

1500000
500000 500000 500000
500000 500000 500000
500000 500000 500000

output:


355543262

result:

ok 1 number(s): "355543262"

Test #5:

score: 0
Accepted
time: 268ms
memory: 66936kb

input:

1499999
499999 499999 500001
499999 499999 500001
499999 499999 500001

output:


934301164

result:

ok 1 number(s): "934301164"

Test #6:

score: 0
Accepted
time: 1099ms
memory: 167920kb

input:

1500000
1 0 1499999
1499999 1 0
0 1499999 1

output:


1500000

result:

ok 1 number(s): "1500000"

Test #7:

score: 0
Accepted
time: 545ms
memory: 101396kb

input:

1499999
0 749999 750000
750000 0 749999
749999 750000 0

output:


713966599

result:

ok 1 number(s): "713966599"

Test #8:

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

input:

1
1 0 0
0 0 1
0 1 0

output:


1

result:

ok 1 number(s): "1"

Test #9:

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

input:

1
0 1 0
0 1 0
0 1 0

output:


1

result:

ok 1 number(s): "1"

Test #10:

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

input:

1
0 0 1
1 0 0
1 0 0

output:

0

result:

ok 1 number(s): "0"

Test #11:

score: 0
Accepted
time: 256ms
memory: 68312kb

input:

1499999
500000 500000 499999
499999 499999 500001
499999 499999 500001

output:


617065435

result:

ok 1 number(s): "617065435"

Test #12:

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

input:

2
1 1 0
0 0 2
0 0 2

output:


0

result:

ok 1 number(s): "0"

Test #13:

score: 0
Accepted
time: 266ms
memory: 70592kb

input:

1500000
500000 500001 499999
499999 500000 500001
499999 500000 500001

output:


925862004

result:

ok 1 number(s): "925862004"

Test #14:

score: 0
Accepted
time: 123ms
memory: 41424kb

input:

629197
210878 201408 216911
145293 266423 217481
194751 220179 214267

output:


447295633

result:

ok 1 number(s): "447295633"

Test #15:

score: 0
Accepted
time: 116ms
memory: 35532kb

input:

579097
200209 204257 174631
149110 148890 281097
138034 263752 177311

output:


71830925

result:

ok 1 number(s): "71830925"

Test #16:

score: 0
Accepted
time: 116ms
memory: 36024kb

input:

354224
100316 63899 190009
69306 123829 161089
140523 76088 137613

output:


44852283

result:

ok 1 number(s): "44852283"

Test #17:

score: 0
Accepted
time: 271ms
memory: 64152kb

input:

1229851
383009 323934 522908
551226 311238 367387
547622 353128 329101

output:


39721313

result:

ok 1 number(s): "39721313"

Test #18:

score: -100
Wrong Answer
time: 229ms
memory: 58104kb

input:

858452
195309 312080 351063
384805 51797 421850
200466 301164 356822

output:


452309441

result:

wrong answer 1st numbers differ - expected: '506491992', found: '452309441'