QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#75614#4922. 生活在对角线下4182_543_73150 1114ms85316kbC++5.4kb2023-02-05 22:06:302023-02-05 22:06:33

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-05 22:06:33]
  • 评测
  • 测评结果:50
  • 用时:1114ms
  • 内存:85316kb
  • [2023-02-05 22:06:30]
  • 提交

answer

#include<cstdio>
using namespace std;
#define N 530001
#define M 11
#define mod 998244353
int pw(int a,int p){int as=1;while(p){if(p&1)as=1ll*as*a%mod;a=1ll*a*a%mod;p>>=1;}return as;}
int fr[N],ifr[N],gr[2][N*2],rev[N*2];
void init(int l=19)
{
	fr[0]=1;for(int i=1;i<=1<<l;i++)fr[i]=1ll*i*fr[i-1]%mod;
	ifr[1<<l]=pw(fr[1<<l],mod-2);for(int i=1<<l;i>=1;i--)ifr[i-1]=1ll*i*ifr[i]%mod;
	for(int s=2;s<=1<<l;s<<=1)for(int i=1;i<s;i++)rev[i+s]=(rev[(i>>1)+s]>>1)+((i&1)*(s>>1));
	for(int t=0;t<2;t++)
	for(int s=2;s<=1<<l;s<<=1)
	{
		int tp=pw(3,(mod-1)/s);
		if(!t)tp=pw(tp,mod-2);
		int vl=1;
		for(int i=0;i<s;i++)gr[t][s+i]=vl,vl=1ll*vl*tp%mod;
	}
}
int f[N],g[N],ntt[N];
void dft(int s,int *a,int t)
{
	for(int i=0;i<s;i++)ntt[rev[i+s]]=a[i];
	for(int l=2;l<=s;l<<=1)
	for(int i=0;i<s;i+=l)
	for(int j=0;j<l>>1;j++)
	{
		int v1=ntt[i+j],v2=1ll*ntt[i+j+(l>>1)]*gr[t][j+l]%mod;
		ntt[i+j]=(v1+v2)%mod;ntt[i+j+(l>>1)]=(v1+mod-v2)%mod;
	}
	int tp=t?1:pw(s,mod-2);
	for(int i=0;i<s;i++)a[i]=1ll*ntt[i]*tp%mod;
}
void polyinv(int n,int *s,int *t)
{
	if(n==1){t[0]=pw(s[0],mod-2);return;}
	polyinv((n+1)>>1,s,t);
	int l=1;while(l<=n*2+4)l<<=1;
	for(int i=0;i<l;i++)f[i]=g[i]=0;
	for(int i=0;i<n;i++)f[i]=s[i],g[i]=t[i];
	dft(l,f,1);dft(l,g,1);for(int i=0;i<l;i++)f[i]=1ll*g[i]*(2+mod-1ll*f[i]*g[i]%mod)%mod;
	dft(l,f,0);
	for(int i=0;i<n;i++)t[i]=f[i];
}

int cl[N],ls[M][N],vl[M][N],fi[M][N],tp[N],rs[N],iri[N],ri[N],c[M][M];
void solve_cl(int n,int p,int q)
{
	for(int i=0;i<=10;i++)c[i][0]=c[i][i]=1;
	for(int i=2;i<=10;i++)for(int j=1;j<i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
	int l=1;while(l<=n*4+3)l<<=1;
	cl[0]=1;for(int i=1;i<=n;i++)cl[i]=1ll*cl[i-1]*(4*i-2)%mod*pw(i+1,mod-2)%mod;
	for(int i=0;i<=n;i++)rs[i]=cl[i];
	dft(l,rs,1);
	for(int a=0;a<=p;a++)for(int b=0;b<=q;b++)
	{
		//ls*rs
		for(int i=0;i<=n;i++)ls[a*(q+1)+b][i]=1ll*cl[i]*pw(i+1,a)%mod*pw(i,b)%mod;
		dft(l,ls[a*(q+1)+b],1);
		for(int i=0;i<l;i++)ls[a*(q+1)+b][i]=1ll*ls[a*(q+1)+b][i]*rs[i]%mod;
		//fi
		for(int i=0;i<=n;i++)fi[a*(q+1)+b][i]=1ll*cl[i]*pw(i,a)%mod*pw(i+1,b)%mod;
		dft(l,fi[a*(q+1)+b],1);
	}
	// / 1-ls_0*x
	dft(l,ls[0],0);
	ri[0]=1;for(int i=1;i<=n;i++)ri[i]=mod-ls[0][i-1];
	polyinv(n+1,ri,iri);
	dft(l,iri,1);
	dft(l,ls[0],1);
	for(int a=0;a<=p;a++)for(int b=0;b<=q;b++)
	{
		for(int i=0;i<l;i++)tp[i]=0;
		//vl_(a,b)=x*(vl_(a,b)+f_i)*ls+c
		if(a+b==0)
		{
			for(int i=0;i<=n;i++)tp[i]=cl[i];
			dft(l,tp,1);
		}
		for(int a1=0;a1<=a;a1++)for(int b1=0;b1<=b;b1++)
		for(int i=0;i<l;i++)tp[i]=(tp[i]+1ll*c[a][a1]*c[b][b1]*gr[1][l+i]%mod*
		(vl[a1*(q+1)+b1][i]+fi[a1*(q+1)+b1][i])%mod*ls[(a-a1)*(q+1)+(b-b1)][i])%mod;
		for(int i=0;i<l;i++)tp[i]=1ll*tp[i]*iri[i]%mod;
		dft(l,tp,0);
		for(int i=0;i<=n;i++)vl[a*(q+1)+b][i]=tp[i];
		dft(l,vl[a*(q+1)+b],1);
	}
}
int ls2[M][N],t1[N];
void solve_c2(int n,int p,int q,int d)
{
	int l=1;while(l<=n*4+3)l<<=1;
	for(int a=0;a<=p;a++)for(int b=0;b<=q;b++)
	{
		for(int i=0;i<=n;i++)ls2[a*(q+1)+b][i]=1ll*(i?1ll*fr[i*2-1]*ifr[i]%mod*ifr[i-1]%mod:1)*pw(i,a+b)%mod;
		dft(l,ls2[a*(q+1)+b],1);
	}
	for(int a=p;a>=0;a--)for(int b=q;b>=0;b--)
	{
		for(int i=0;i<l;i++)vl[a*(q+1)+b][i]=1ll*vl[a*(q+1)+b][i]*ls2[0][i]%mod;
		for(int a1=0;a1<=a;a1++)for(int b1=0;b1<=b;b1++)if(a1+b1<a+b)
		for(int i=0;i<l;i++)vl[a*(q+1)+b][i]=(vl[a*(q+1)+b][i]+1ll*c[a][a1]*c[b][b1]*
		vl[a1*(q+1)+b1][i]%mod*ls2[(a-a1)*(q+1)+(b-b1)][i]%mod)%mod;
	}
	for(int i=0;i<=n;i++)t1[i]=i?1ll*fr[2*i+d-1]*ifr[i+d-1]%mod*ifr[i]%mod:1;
	dft(l,t1,1);
	for(int a=p;a>=0;a--)for(int b=q;b>=0;b--)
	{
		for(int i=0;i<l;i++)vl[a*(q+1)+b][i]=1ll*vl[a*(q+1)+b][i]*t1[i]%mod;
		dft(l,vl[a*(q+1)+b],0);
	}
}
int al[M][N],s1[M][M],t2[N];
void solve_a1(int n,int p,int q,int c)
{
	int l=1;while(l<=n*2+3)l<<=1;
	for(int i=0;i<=n;i++)t2[i]=1ll*fr[2*i+c]*ifr[i+c]%mod*ifr[i]%mod;
	dft(l,t2,1);
	for(int a=0;a<=p;a++)for(int b=0;b<=q;b++)
	{
		for(int i=0;i<=n;i++)al[a*(q+1)+b][i]=1ll*fr[i*2]*ifr[i]%mod*ifr[i]%mod*pw(i,a+b)%mod;
		dft(l,al[a*(q+1)+b],1);
		for(int i=0;i<l;i++)al[a*(q+1)+b][i]=1ll*al[a*(q+1)+b][i]*t2[i]%mod;
		dft(l,al[a*(q+1)+b],0);
	}
	s1[0][0]=1;
	for(int i=1;i<=10;i++)for(int j=1;j<=i;j++)s1[i][j]=1ll*j*(s1[i-1][j]+s1[i-1][j-1])%mod;
	for(int i=0;i<=n;i++)
	for(int a=0;a<=p&&a<=i;a++)for(int b=0;b<=q&&b<=i+c;b++)
	{
		int si=1ll*ifr[a]%mod*ifr[b]%mod*ifr[i-a]%mod*ifr[i+c-b]%mod*fr[i*2+c]%mod;
		if(a<i)si=(si+1ll*ifr[a]%mod*ifr[b]%mod*ifr[i-a-1]%mod*ifr[i+c-b]%mod*fr[i*2+c]%mod*ifr[a+b+1]%mod*fr[a+b])%mod;
		if(b<i+c)si=(si+1ll*ifr[a]%mod*ifr[b]%mod*ifr[i-a]%mod*ifr[i+c-b-1]%mod*fr[i*2+c]%mod*ifr[a+b+1]%mod*fr[a+b])%mod;
		for(int a2=a;a2<=p;a2++)for(int b2=b;b2<=q;b2++)
		al[a2*(q+1)+b2][i]=(al[a2*(q+1)+b2][i]+1ll*s1[a2][a]*s1[b2][b]*si)%mod;
	}
}
int T,d,p,q,n,fg,v[M][M],m;
int main()
{
	scanf("%d%d%d%d%d",&T,&d,&p,&q,&n);
	init();
	if(d<0)p^=q^=p^=q,d*=-1,fg=1;
	solve_cl(n,p,q);
	solve_c2(n,p,q,d);
	if(fg)solve_a1(n,p,q,d);
	while(T--)
	if(fg)
	{
		int as=0;
		scanf("%*d%d",&m);
		for(int i=0;i<=q;i++)for(int j=0;j<=p;j++)scanf("%d",&v[j][i]);
		for(int i=0;i<=p;i++)for(int j=0;j<=q;j++)as=(as+1ll*v[i][j]*(al[i*(q+1)+j][m]+mod-vl[i*(q+1)+j][m]))%mod;
		printf("%d\n",as);
	}
	else
	{
		int as=0;
		scanf("%d%*d",&m);
		for(int i=0;i<=p;i++)for(int j=0;j<=q;j++)scanf("%d",&v[i][j]);
		for(int i=0;i<=p;i++)for(int j=0;j<=q;j++)as=(as+1ll*v[i][j]*vl[i*(q+1)+j][m])%mod;
		printf("%d\n",as);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 1
Accepted

Test #1:

score: 1
Accepted
time: 24ms
memory: 24952kb

input:

1 -10 1 2 1000
825 815
107973512 400177523 812303207
164088430 603506669 337780072

output:

360076089

result:

ok 1 number(s): "360076089"

Test #2:

score: 0
Accepted
time: 22ms
memory: 25200kb

input:

1 424 1 4 576
130 554
926445673 393820912 634481616 292175028 733650737
100427548 899689095 876811717 849191704 696040532

output:

564712546

result:

ok 1 number(s): "564712546"

Test #3:

score: 0
Accepted
time: 28ms
memory: 22916kb

input:

1 -171 2 1 1000
805 634
250066876 719653007
284194184 531322789
491311782 185842441

output:

910556244

result:

ok 1 number(s): "910556244"

Test #4:

score: 0
Accepted
time: 24ms
memory: 25196kb

input:

1 11 4 1 989
142 153
581558550 138798754
575233123 788754497
582314564 303591688
635874631 658261955
615116681 498307457

output:

918405181

result:

ok 1 number(s): "918405181"

Test #5:

score: 0
Accepted
time: 26ms
memory: 26988kb

input:

1 -87 1 2 1000
164 77
264180617 338145439 610918500
800846696 216126209 112962819

output:

629819261

result:

ok 1 number(s): "629819261"

Subtask #2:

score: 9
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 9
Accepted
time: 115ms
memory: 26956kb

input:

100000 -99 2 1 1000
712 613
238230707 820405654
473765646 826816733
751513618 421153458
209 110
22075351 398854663
148159396 487281124
972932017 200517786
383 284
22252771 205525630
491328752 607545155
561318911 135661425
929 830
156478040 89922795
380802607 32081978
898588032 110586958
956 857
4206...

output:

863094157
570366074
281608243
247495628
396961441
855444791
694374848
782506902
280202079
688077364
610676536
115373962
360154110
834242083
887647721
164293717
759683961
710870451
213441970
863772654
514218158
532711794
558875294
421795761
517787006
458381459
506983637
742686106
435175768
111255264
...

result:

ok 100000 numbers

Test #7:

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

input:

100000 252 3 1 748
130 382
311369319 709099006
49474431 724072531
761415026 251406187
389170658 169808960
581 833
89779535 938252574
504798466 677842435
654289171 763708659
719082912 762770851
691 943
571693157 187035992
300995260 403041189
726726538 63983502
814000657 315732021
121 373
339102104 42...

output:

516270157
614211606
655396807
981733406
752565578
312973289
850750616
826813023
753739511
227580123
199177890
403714939
559334967
370464926
363937285
583678656
239132195
834163477
111915553
68813179
875627540
299872127
660063389
31474925
464946255
125818391
645016505
267670615
440441568
356463850
84...

result:

ok 100000 numbers

Test #8:

score: 0
Accepted
time: 157ms
memory: 27148kb

input:

100000 195 2 2 805
325 520
266481322 663615421 428019284
968378746 158386978 211891009
161987045 142931644 790431809
621 816
756898302 952132541 196745128
424307295 926376261 130425563
604844618 645296808 252920984
60 255
873310227 887037637 787608776
98214115 355810775 242821836
537250851 650821017...

output:

922269244
757786754
400099571
332972619
780501723
469958234
540206804
924583388
519189002
566620024
244468115
73221163
663221021
159111716
451144022
658783977
656844692
831466434
186871631
60740257
542611012
773315130
755261907
193772041
628947709
363111530
452621670
349808610
264947076
342250907
16...

result:

ok 100000 numbers

Subtask #3:

score: 20
Accepted

Test #9:

score: 20
Accepted
time: 319ms
memory: 42772kb

input:

1 4683 0 0 95317
86560 91243
412303217

output:

952052072

result:

ok 1 number(s): "952052072"

Test #10:

score: 0
Accepted
time: 384ms
memory: 44844kb

input:

1 -24796 0 0 100000
93338 68542
849332154

output:

980840409

result:

ok 1 number(s): "980840409"

Test #11:

score: 0
Accepted
time: 162ms
memory: 33576kb

input:

1 40156 0 0 59844
39551 79707
566086447

output:

620552907

result:

ok 1 number(s): "620552907"

Test #12:

score: 0
Accepted
time: 381ms
memory: 44820kb

input:

1 -714 0 0 100000
72672 71958
817542139

output:

799272798

result:

ok 1 number(s): "799272798"

Test #13:

score: 0
Accepted
time: 325ms
memory: 42664kb

input:

1 23418 0 0 76582
6862 30280
442920403

output:

642352133

result:

ok 1 number(s): "642352133"

Test #14:

score: 0
Accepted
time: 160ms
memory: 33444kb

input:

1 42983 0 0 57017
42753 85736
380012689

output:

828068267

result:

ok 1 number(s): "828068267"

Test #15:

score: 0
Accepted
time: 363ms
memory: 46868kb

input:

1 -25448 0 0 100000
47466 22018
617788426

output:

485886943

result:

ok 1 number(s): "485886943"

Test #16:

score: 0
Accepted
time: 373ms
memory: 46860kb

input:

1 -35138 0 0 100000
49912 14774
472000456

output:

323681794

result:

ok 1 number(s): "323681794"

Test #17:

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

input:

1 15928 0 0 84072
57657 73585
31014982

output:

184096139

result:

ok 1 number(s): "184096139"

Test #18:

score: 0
Accepted
time: 332ms
memory: 43772kb

input:

1 5316 0 0 94684
36186 41502
601085246

output:

51887433

result:

ok 1 number(s): "51887433"

Subtask #4:

score: 20
Accepted

Dependency #3:

100%
Accepted

Test #19:

score: 20
Accepted
time: 189ms
memory: 34716kb

input:

100000 43925 0 0 56075
36770 80695
880793638
55133 99058
946571985
27169 71094
601132030
42027 85952
954509221
1261 45186
326012305
12030 55955
997023025
9914 53839
788665071
39921 83846
193760311
25774 69699
584278712
28428 72353
45133606
32564 76489
40466335
35483 79408
491164633
1587 45512
842380...

output:

332757564
673855662
612475468
823636534
480158617
642667251
497333900
509207503
811150980
417148607
922658720
104640134
806209587
173065009
605751740
862381731
38248058
821044620
841331399
289617079
251770008
141909273
16627417
373489864
231237810
941325561
178798279
674579054
924181592
61271475
964...

result:

ok 100000 numbers

Test #20:

score: 0
Accepted
time: 408ms
memory: 46448kb

input:

100000 -24410 0 0 100000
88811 64401
883320435
98680 74270
679694811
25736 1326
585801443
58045 33635
248117495
75671 51261
370680099
54439 30029
971994977
59364 34954
824527105
83366 58956
743467199
86814 62404
560320056
79263 54853
982330282
31352 6942
755041686
56396 31986
625187969
95451 71041
6...

output:

944753157
183242929
363439527
347484131
162238407
874219996
466587038
69445583
299052607
25676433
596600163
562511304
969440848
734888105
717978251
646284734
285785033
177137639
757127623
981404389
646133036
419072122
570786562
49543639
324434058
643959988
425580060
576826099
385768604
231992533
414...

result:

ok 100000 numbers

Test #21:

score: 0
Accepted
time: 385ms
memory: 46848kb

input:

100000 -5861 0 0 100000
16952 11091
854232561
61287 55426
808396787
36941 31080
498670332
78084 72223
125065027
77939 72078
113005933
66811 60950
561023395
8690 2829
85984152
86780 80919
73284065
24701 18840
962634657
49186 43325
820164989
13544 7683
181059009
82733 76872
475302128
59169 53308
30753...

output:

953252694
312702564
226453117
67575786
903898714
513740725
876463803
777825703
146006471
2374918
297784488
386629852
320437877
988885626
718795318
32469771
761373569
413225682
535374528
890489090
946876926
547336815
741402601
164218598
624314043
440338456
358510966
78123388
844278570
353784116
33016...

result:

ok 100000 numbers

Test #22:

score: 0
Accepted
time: 194ms
memory: 36548kb

input:

100000 36351 0 0 63649
63623 99974
215842464
38932 75283
281762844
36628 72979
412528519
32243 68594
274539771
12583 48934
35262820
58794 95145
584821840
55654 92005
405023451
54594 90945
121054191
13799 50150
945750972
3396 39747
123637787
24436 60787
60557209
28533 64884
16469063
62629 98980
97582...

output:

174547901
368722952
48857280
38439764
222892265
312334973
776332784
870332855
155759525
948664848
557524993
498142735
312543625
96578298
812380665
262256294
625974911
11727861
934671647
410990281
662266734
602386252
129790362
105856770
514479617
606174145
351070683
902755038
185658666
319441312
6292...

result:

ok 100000 numbers

Test #23:

score: 0
Accepted
time: 397ms
memory: 45572kb

input:

100000 -30740 0 0 100000
68807 38067
675336699
46303 15563
123039099
67930 37190
232230088
54579 23839
35352609
92730 61990
284529851
67176 36436
665212494
57299 26559
133796107
49959 19219
33773652
84236 53496
372759887
99484 68744
426876149
34577 3837
572112278
61585 30845
172184077
77857 47117
90...

output:

36920501
226235095
750211143
333187562
373628984
295265220
37657937
466124753
990905489
551665113
446537030
431018050
86173594
169742883
218477019
236694053
535757873
691309698
571533347
44799594
978410954
207318736
924231440
714349634
256005837
765738237
355457430
213887617
753194413
829442039
4620...

result:

ok 100000 numbers

Test #24:

score: 0
Accepted
time: 384ms
memory: 46144kb

input:

100000 -38460 0 0 100000
51513 13053
225553548
46939 8479
742237301
76548 38088
403832837
58372 19912
532371282
69056 30596
227486715
57631 19171
992007340
43442 4982
456446541
98517 60057
139482341
93593 55133
617856070
94670 56210
632588368
61305 22845
540079128
42989 4529
243030634
61305 22845
60...

output:

264377260
988347451
122980170
868000378
424450627
937049667
82203152
65434176
511951571
866041634
172830523
592267120
339840284
510003002
301057898
661439490
614715916
352897087
347380257
99947743
217323734
533045349
197971764
276536330
181518107
810369320
38076519
795663640
628535813
745310656
9165...

result:

ok 100000 numbers

Test #25:

score: 0
Accepted
time: 400ms
memory: 45824kb

input:

100000 -21781 0 0 100000
98045 76264
260148888
51675 29894
775592370
96562 74781
6673060
61291 39510
561247689
51571 29790
374708153
56745 34964
902344534
38026 16245
499287321
46349 24568
80542300
44223 22442
235391104
44474 22693
180934225
73722 51941
571180203
98775 76994
186933783
37624 15843
66...

output:

403860096
918023019
505862766
325574001
758856670
454849577
390589711
142177895
563486806
252645563
120628328
553587845
992851487
933771813
401873497
993790093
184884214
294133840
346874311
513672329
312442149
595232497
772328343
814181956
380438506
927087216
253560503
970622427
910857175
430512071
...

result:

ok 100000 numbers

Subtask #5:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Dependency #3:

100%
Accepted

Test #26:

score: 0
Time Limit Exceeded

input:

1 -40679 1 3 100000
75191 34512
321693501 896183087 224533692 282076683
38691763 630172019 273852722 127891101

output:


result:


Subtask #6:

score: 0
Time Limit Exceeded

Test #41:

score: 10
Accepted
time: 1114ms
memory: 85316kb

input:

100000 0 2 1 100000
48964 48964
666670967 90494987
74847122 615108201
29533064 582540229
14418 14418
391779909 223696706
701170191 885097597
551643398 25626747
81584 81584
951326734 520293397
13860946 896899117
821166399 282263457
76849 76849
598606953 879771697
930252135 671750715
673503431 3060699...

output:

513261452
727599133
935022075
486566245
581605882
190874624
492903919
212718785
390117408
13902475
85548183
635628561
482394025
962073695
362740677
938001783
889953951
725536236
308635636
699865601
901798869
464425652
743201170
92575030
846809630
169046922
528318328
181301191
961103497
451810607
792...

result:

ok 100000 numbers

Test #42:

score: -10
Time Limit Exceeded

input:

100000 0 4 1 100000
62874 62874
118183474 407193132
685767410 687439227
635193908 610100986
258734574 238431118
899478481 761001837
51740 51740
444395131 500444257
428937362 53260346
30808281 906820217
513141079 288839678
554203046 663643475
35914 35914
356034890 347998675
273353479 349503145
372514...

output:


result:


Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

0%