QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#43744#2834. NonsensexiaoyaowudiAC ✓564ms101596kbC++142.1kb2022-08-10 16:45:222022-08-10 16:45:24

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-10 16:45:24]
  • 评测
  • 测评结果:AC
  • 用时:564ms
  • 内存:101596kb
  • [2022-08-10 16:45:22]
  • 提交

answer

#include <cstdio>
#include <algorithm>
using namespace std;
constexpr int N=5010,p=998244353;
int inv[N<<1],n,x,y,q,fac[N<<1],ifac[N<<1];
int fp(int a,int b){int ans=1,off=a;while(b){if(b&1) ans=1ll*ans*off%p;off=1ll*off*off%p;b>>=1;}return ans;}
int calc(int m,int k,int a){
	static int df[N<<1];
	df[0]=1;
	for(int i=1;i<=k;++i) df[i]=1ll*df[i-1]*(m+i)%p*inv[i]%p;
	int val=fp(p+1-a,p-2),ans=0;
	for(int i=0,j=1;i<=k;++i,j=1ll*j*val%p){
		ans=(ans+1ll*df[k-i]*j)%p;
	}
	ans=(fp(val,k)-1ll*ans*fp(a,m+1))%p;
	ans=1ll*val*(ans+p)%p;
	return ans;
}
int main(){
	inv[1]=1;
	for(int i=2;i<(N<<1);++i) inv[i]=1ll*inv[p%i]*(p-p/i)%p;
	fac[0]=ifac[0]=1;
	for(int i=1;i<(N<<1);++i) fac[i]=1ll*fac[i-1]*i%p,ifac[i]=1ll*ifac[i-1]*inv[i]%p;
	while(scanf("%d%d%d%d",&n,&x,&y,&q)!=EOF){
		int k=1ll*x*fp(y,p-2)%p;
		int mxa=0,mxb=0;
		constexpr int Q=200010;
		static int qs[Q][2];
		for(int i=1;i<=q;++i){
			scanf("%d%d",&qs[i][0],&qs[i][1]);
			mxa=max(mxa,qs[i][0]);
			mxb=max(mxb,qs[i][1]);
		}
		if(!x || !y){
			static int nfac[N<<1],nifac[N<<1];
			nfac[0]=nifac[0]=1;
			for(int i=1;i<=mxa+mxb+1;++i) nfac[i]=1ll*nfac[i-1]*(n-i+1)%p,nifac[i]=1ll*nifac[i-1]*fp(n-i+1,p-2)%p;
			for(int i=1;i<=q;++i){
				int a=qs[i][0],b=qs[i][1];
				if(a+b==n){printf("1\n");}
				else{
					int ans=(1ll*nfac[a+b]*nifac[a]%p*ifac[b]%p*fp(y,n-a-b)
							+1ll*nfac[a+b]*nifac[b]%p*ifac[a]%p*fp(x,n-a-b))%p;
					printf("%d\n",ans);
				}
			}
			continue;
		}
		if(k==1){
			static int df[N<<1];
			df[0]=1;
			for(int i=1;i<=mxa+mxb+1;++i) df[i]=1ll*df[i-1]*inv[i]%p*(n-i+2)%p;
			for(int i=1;i<=q;++i){
				printf("%lld\n",1ll*df[qs[i][0]+qs[i][1]+1]*fp(x,n-qs[i][0]-qs[i][1])%p);
			}
			continue;
		}
		static int f[N][N];
		for(int i=0;i<=mxa;++i){
			f[i][0]=calc(n-i,i,k);
		}
		int ik=fp(k,p-2);
		for(int i=1;i<=mxb;++i){
			f[0][i]=1ll*calc(n-i,i,ik)*fp(k,n-i)%p;
		}
		int val=fp(k-1,p-2);
		for(int i=1;i<=mxa;++i) for(int j=1;j<=mxb;++j) if(i+j<=n){
			f[i][j]=1ll*val*(f[i][j-1]-f[i-1][j]+p)%p;
		}
		for(int i=1;i<=q;++i) printf("%lld\n",1ll*f[qs[i][0]][qs[i][1]]*fp(y,n-qs[i][0]-qs[i][1])%p);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3848kb

input:

3 1 2 2
1 1
1 2
100 2 3 1
1 1

output:

6
1
866021789

result:

ok 3 lines

Test #2:

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

input:

1000000000 0 1 1
1000 1000
2 0 0 1
1 1
2 998244352 998244352 1
1 1

output:

381781645
1
1

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 465ms
memory: 99752kb

input:

1000000000 998244351 998244352 1
5000 5000

output:

663228915

result:

ok single line: '663228915'

Test #4:

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

input:

105886041 9 3 200
4 3
5 1
1 1
4 1
3 3
1 5
2 1
1 5
2 1
1 5
3 3
4 4
2 1
4 4
1 2
5 2
5 2
2 5
4 5
3 3
4 3
1 4
3 1
5 4
5 3
5 2
5 3
3 3
1 3
4 3
2 3
3 5
1 3
3 5
2 3
4 4
3 4
5 5
2 3
1 1
3 3
4 2
1 4
4 5
2 3
1 5
2 2
4 2
5 5
2 1
4 3
3 3
3 1
2 1
2 5
1 1
4 4
1 5
1 5
3 1
3 2
2 2
4 1
5 5
3 4
2 2
2 1
5 3
5 3
2 2
1 ...

output:

721440251
764408668
442427888
914530150
115811774
360614503
666106268
360614503
666106268
360614503
115811774
166867820
666106268
166867820
985976063
717651702
717651702
405340273
435048189
115811774
721440251
719754512
660548079
998056822
165742634
717651702
165742634
115811774
407319461
721440251
...

result:

ok 200000 lines

Test #5:

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

input:

405229773 25 79 200
3 3
5 5
5 5
1 5
2 4
2 4
3 1
3 3
5 4
1 5
2 1
3 1
4 1
2 5
1 4
4 4
4 1
5 5
5 3
2 2
1 1
2 1
4 2
4 4
2 3
5 1
4 3
2 3
3 4
4 3
2 2
3 3
1 4
5 3
2 2
3 1
1 1
3 3
3 5
1 3
5 2
1 1
1 4
5 5
5 5
4 1
2 5
2 5
1 4
1 1
3 3
5 4
1 2
1 1
2 5
4 3
5 4
3 3
5 2
3 3
4 1
2 3
2 5
1 3
4 3
4 4
4 2
5 1
2 5
3 5
...

output:

52820293
692687559
692687559
899722361
150221007
150221007
570819646
52820293
9962865
899722361
594892845
570819646
90708097
161767707
25275214
680941576
90708097
692687559
142946866
827907378
868929596
594892845
73037078
680941576
897540013
658419918
202971687
897540013
38775730
202971687
827907378...

result:

ok 200000 lines

Test #6:

score: 0
Accepted
time: 67ms
memory: 3848kb

input:

205514256 631068448 638301474 200
2 5
2 4
1 4
1 5
4 2
1 5
4 2
1 2
5 4
3 2
3 5
4 3
2 4
4 5
3 2
5 5
1 1
3 2
3 2
5 2
4 2
4 3
4 2
3 5
2 4
5 1
2 1
2 3
3 1
5 1
3 1
1 3
2 5
5 4
4 5
2 1
5 4
5 1
2 3
5 3
5 2
1 2
2 2
5 2
2 4
1 1
3 1
1 3
4 4
2 3
1 2
2 4
1 1
1 5
3 5
2 2
2 2
1 5
2 5
5 2
2 5
3 1
1 3
5 1
5 3
2 3
3 ...

output:

372109930
532818312
880334055
931386950
851000884
931386950
851000884
920232088
545949965
457738522
874230202
29735043
532818312
831616270
457738522
744561645
232363848
457738522
457738522
18438814
851000884
29735043
851000884
874230202
532818312
870223579
812363425
209681041
864355959
870223579
864...

result:

ok 200000 lines

Test #7:

score: 0
Accepted
time: 79ms
memory: 4020kb

input:

371075301 713524167 984212326 2000
28 33
40 18
14 29
49 43
10 39
45 38
32 38
19 31
24 12
35 41
8 19
41 9
19 42
20 28
36 6
3 29
28 44
35 38
5 22
26 12
13 47
8 30
38 32
12 21
36 25
45 46
50 50
22 9
5 31
14 10
30 13
36 2
33 12
17 24
18 45
3 47
37 25
50 13
26 25
11 4
22 34
18 6
31 36
43 27
18 22
12 16
3...

output:

35509436
159833571
484242097
119046197
513595595
812038704
406494518
52232286
582008066
546786732
389948063
577535640
846537158
493495311
405937265
461091227
835518929
219508439
149463993
145136822
152212306
669088231
12828040
963047886
771023770
274264976
352767249
37662120
746104740
848752621
5766...

result:

ok 200000 lines

Test #8:

score: 0
Accepted
time: 102ms
memory: 6348kb

input:

326744271 690638130 696925215 20000
298 465
150 111
63 22
485 492
226 239
467 478
334 287
400 367
457 199
263 401
456 457
435 390
473 368
203 88
439 365
427 317
429 216
177 287
139 204
413 301
212 155
37 209
262 72
461 488
237 15
384 485
124 217
129 490
346 61
447 89
347 404
210 241
321 425
264 227
...

output:

320182528
885037169
987260454
567004035
675906158
296063037
102545299
839780836
55989828
968396611
608553216
520690730
757453601
987339585
479505716
407039045
797684534
963385288
1943856
788131468
382178517
221019084
438142020
219895722
224755828
311507010
127291193
52822780
618671283
854120409
5053...

result:

ok 200000 lines

Test #9:

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

input:

436870970 392052048 645851299 200000
4938 818
1523 3467
973 4383
3788 2554
4471 1017
4676 1623
177 2249
3721 211
3492 3954
3252 4140
2971 4325
688 1381
3780 2479
1145 2483
3467 4343
2162 4705
3191 4416
2805 4917
4883 853
3824 4889
3910 4856
3082 2723
4156 921
1154 4685
226 1293
1120 237
2829 349
441...

output:

9544620
518912284
541614157
372073856
362578361
426236025
377863983
425477712
434770014
467638442
62493689
954484988
745559578
551774553
873609004
96439247
749859094
516502191
615526243
205247799
796287550
274795834
944667137
118164303
98105707
288964279
244923144
643945654
929130123
302481429
88253...

result:

ok 200000 lines

Test #10:

score: 0
Accepted
time: 536ms
memory: 101520kb

input:

175875716 410144900 97097634 200000
1711 72
299 4642
4961 1242
674 698
4214 1107
4622 1946
3094 4971
471 933
1245 2703
3733 2457
4650 886
1705 2898
2833 2599
1823 901
1842 3930
595 1814
88 4146
176 4450
3098 3442
4234 3374
3365 3044
1870 2238
3400 1539
1917 2798
3470 2091
2237 429
2768 4235
1039 837...

output:

180285591
728667493
109737898
720984986
279445479
180498901
783848532
604344419
536446846
224995985
665917962
929673586
208787825
531073777
806621604
473352896
279811957
709558012
901741246
903915284
782351989
864288830
807962018
309859544
896705274
116347208
156158893
632184733
808685122
308565845
...

result:

ok 200000 lines

Test #11:

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

input:

859419071 629138239 126993191 200000
3981 463
837 1387
2908 3764
1344 4633
3278 2882
4600 2969
1962 137
15 55
2512 3969
3870 1166
3169 1093
800 1192
2522 1203
4317 1487
2598 3813
960 1840
4705 314
49 1347
1165 2293
1188 4
2465 1709
1993 2181
4757 4332
3794 3282
967 1657
3671 4523
3649 4262
2909 1165...

output:

867756937
422135696
915428024
787433162
129438614
977942587
262760809
699704848
218165309
156252640
271212750
871880284
905128694
132897747
963078461
328290579
894081009
486573486
626892225
253590588
54373830
621621839
25899231
740661396
831635457
350219485
202746694
363446530
42306428
72765588
6762...

result:

ok 200000 lines

Test #12:

score: 0
Accepted
time: 539ms
memory: 101548kb

input:

598423817 647231091 44265481 200000
3459 4716
4614 2562
1896 2920
2822 72
3021 676
4137 3292
4879 4756
4469 3073
265 2718
2456 3675
4040 4142
1008 413
2383 1323
4187 3009
2868 3400
4393 845
113 2748
124 2096
3572 2586
1599 3489
4623 4898
2268 2097
3593 3054
2260 4099
1914 3942
2492 2419
3587 852
223...

output:

791096233
178462366
141648872
918959026
235387354
847317505
843825690
9971812
744172110
649326488
392449327
158673420
659808836
921794689
625511457
481383673
478884995
6695377
830706196
107832629
701458719
814597110
658276482
670012724
271314136
124430361
198729895
355483258
804986985
37922226
99642...

result:

ok 200000 lines

Test #13:

score: 0
Accepted
time: 552ms
memory: 101500kb

input:

192204371 967313827 191766284 200000
2936 4778
4878 4546
884 2075
2005 3216
869 766
570 2807
2796 2478
2027 3795
4506 658
233 4288
3424 2999
1217 1930
1436 635
1354 2236
1243 1499
529 250
4713 3966
2495 4334
4491 2879
521 4270
1781 3087
3352 1612
2837 3672
4919 317
3262 3931
2120 3419
1629 2443
1151...

output:

282379762
255110320
568369113
208637836
91715322
496993246
833845378
443539517
576369315
165018943
690210396
485433774
145676324
966157682
468232499
717280774
89510141
219976903
214885574
383114869
343746454
298772564
719929421
613677811
230732800
612123621
817733005
686526412
338229708
473980891
72...

result:

ok 200000 lines

Test #14:

score: 0
Accepted
time: 519ms
memory: 101268kb

input:

931209116 289152210 339267087 200000
2414 1327
3655 721
4872 3935
1187 3655
613 857
107 3130
2610 2097
1482 1814
4155 2111
715 1797
103 4560
2233 1152
4001 756
1224 654
4217 1086
3961 62
121 1399
274 1571
4193 3980
3636 859
1236 2083
4435 720
2081 1586
2578 1135
18 4320
3644 4019
1568 1330
2772 2922...

output:

844307260
443661987
375183620
124021238
801293954
147207268
439051822
858224855
181810697
713309471
345525147
58193678
860288759
183544438
756853384
711878600
366391096
853795832
142325545
420328734
816066001
333877562
495706902
7555389
714692701
651788433
395511144
992425771
357059675
105457951
217...

result:

ok 200000 lines

Test #15:

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

input:

935055078 609234946 486767891 200000
3788 581
2432 408
1564 3090
369 1799
356 3651
1541 2645
527 4819
1336 4832
4203 860
4301 4307
4486 1121
145 373
1158 2364
1094 4880
295 673
98 2171
2017 1129
2645 3809
4304 4272
4046 1640
3394 272
3223 235
917 2204
1045 4249
4070 4309
4761 4211
3802 2921
4393 107...

output:

827268417
488412806
156864510
234209553
600454885
622031861
433517368
322539114
643044201
479878252
790248245
670307759
823038517
106845259
490980255
710789898
265216733
303289089
49384408
631647611
839000701
849222238
356706941
510423522
845130291
485410691
594123084
711149423
268649614
428756332
7...

result:

ok 200000 lines

Test #16:

score: 0
Accepted
time: 534ms
memory: 101552kb

input:

528835632 627327798 634268694 200000
3265 642
2697 4688
2848 2246
4551 4535
100 1037
1078 2968
3444 4437
790 554
1148 4608
2079 2624
1165 4978
3057 1890
2915 188
964 4106
2862 668
826 1176
130 859
2720 1047
2519 3077
2969 125
2041 4269
4307 4343
160 3630
999 2362
2314 4699
2093 4403
1037 4512
2910 1...

output:

282849035
339868804
439122742
422331208
253830709
236239323
273429778
703276409
192263399
17757910
645722648
766282359
916219254
203412052
910943291
566162741
52662427
400927060
744194766
94615021
974568793
6461715
657134975
258857026
448413351
285785539
766473691
910000099
120023891
539522265
49261...

result:

ok 200000 lines

Test #17:

score: 0
Accepted
time: 539ms
memory: 101596kb

input:

267840377 947410534 551540983 200000
447 4896
1474 3567
4540 4105
3734 782
2139 1935
215 2483
1361 2160
1052 1276
1197 2549
2152 2837
4740 3835
3266 1111
2776 4501
3131 4820
3940 1063
1962 989
4730 3293
2795 3284
2629 3370
3379 1714
1495 2457
2286 1154
4404 1544
2170 476
1365 4688
913 2299
975 2590
...

output:

123313334
933796559
241675810
204150508
236363652
278947568
89412138
698739296
559851004
385273726
681423583
45926821
844104100
523155595
228782713
132582995
772616450
924000898
518924970
122737539
539006829
270233102
306257287
158602839
950515800
275256965
687957777
143941024
862576015
894449347
40...

result:

ok 200000 lines

Test #18:

score: 0
Accepted
time: 560ms
memory: 101552kb

input:

861620931 269248917 699041787 200000
4924 2661
2546 550
3528 3261
2916 3926
2691 4730
4752 2806
4278 4882
2803 1998
438 4001
738 347
1420 396
4282 2628
4933 1109
3001 1750
1915 650
395 394
2434 3022
166 3226
36 1767
2302 2495
3654 646
3370 2966
3240 2162
2125 3590
3121 1973
542 195
3209 4181
1152 28...

output:

673477646
167372996
923615488
227417271
845305746
986413222
591141348
516204018
55507233
740996504
649865339
450187141
759416023
660719017
67181244
667284369
940752116
147724773
709110797
808227949
408434865
821601168
706009731
661237954
58233624
10316900
571192907
578830380
778250341
305686949
6749...

result:

ok 200000 lines