QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#142003	#4916. 抽奖机	crazy_sea	100 ✓	196ms	42236kb	C++11	2.7kb	2023-08-18 10:39:00	2023-08-18 10:39:04

Judging History

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

[2023-08-18 10:39:04]
评测

测评结果：100
用时：196ms
内存：42236kb

查看

[2023-08-18 10:39:00]
提交

answer

#include<cstdio>
#define ll long long
using namespace std;
const int g1=115381398,g2=884618610,mod=1e9+9,N=130;
ll fastpow(ll a,int b)
{
	ll s=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1) s=s*a%mod;
	return s;
}
ll f[N][N],g[N][N],s[N][N],fac[N],ifac[N],k;
ll h[N][N][N],t1[N][N][N],t2[N][N][N];
int n,m,t[N][N];
void pls(ll &a,ll b){a=(a+b)%mod;}
int main()
{
	scanf("%d%d%lld",&n,&m,&k);
	fac[0]=ifac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
	ifac[n]=fastpow(fac[n],mod-2)%mod;
	for(int i=n-1;i;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
	if(k>0) k=(k-1)%(mod-1)+1;
	for(int i=1,x,y;i<=m;i++)
		scanf("%d%d",&x,&y),t[x][y]++;
	for(int i=0;i<=n;i++)
		for(int j=0;j+i<=n;j++)
			for(int k=0;i+j+k<=n;k++)
				h[i][j][k]=fac[i+j+k]*ifac[i]%mod*ifac[j]%mod*ifac[k]%mod;
	for(int i=n;i>=0;i--)
	{
		for(int j=0;j<=n-i;j++)
			for(int x=0;x<=n-i-j;x++)
				for(int y=0;x+y<=n-i-j;y++)
					t1[j][x][y]=t2[j][x][y],t2[j][x][y]=0;
		for(int j=n-i;j>=0;j--)
		{
			int m=n-i-j;
			t[i][j]=t[i][j]*fac[n]%mod*ifac[m]%mod*ifac[i+j]%mod;
			for(int x=0;x<=m;x++)
				for(int y=0;x+y<=m;y++)
					pls(t1[j][x][y],t[i][j]*h[x][y][m-x-y]);
			for(int x=0;x<=m;x++)
				for(int y=0;x+y<=m;y++)
				{
					pls(t2[j][x+1][y],t1[j][x][y]*g1);
					pls(t2[j][x][y+1],t1[j][x][y]*g2);
					pls(t2[j][x][y],t1[j][x][y]);
					if(j)
					{
						pls(t1[j-1][x+1][y],t1[j][x][y]*g2);
						pls(t1[j-1][x][y+1],t1[j][x][y]*g1);
						pls(t1[j-1][x][y],t1[j][x][y]);
					}
				}
		}
	}
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n-i;j++) f[i][j]=t1[0][i][j]*fastpow(h[i][j][n-i-j],mod-2)%mod;
	for(int i=0;i<=n;i++)
		for(int j=0;j+i<=n;j++)
			f[i][j]=fastpow(f[i][j],k)%mod;
	for(int i=0;i<=n+1;i++)
		for(int j=0;j<=n+1;j++)
			for(int k=0;k<=n+1;k++) t2[i][j][k]=t1[i][j][k]=0;
	for(int i=n;i>=0;i--)
	{
		for(int j=0;j<=n-i;j++)
			for(int x=0;x<=n-i-j;x++)
				for(int y=0;x+y<=n-i-j;y++)
					t1[j][x][y]=t2[j][x][y],t2[j][x][y]=0;
		for(int j=n-i;j>=0;j--)
		{
			int m=n-i-j;
			f[i][j]=f[i][j]*fac[n]%mod*ifac[m]%mod*ifac[i+j]%mod;
			for(int x=0;x<=m;x++)
				for(int y=0;x+y<=m;y++)
					pls(t1[j][x][y],f[i][j]*h[x][y][m-x-y]);
			for(int x=0;x<=m;x++)
				for(int y=0;x+y<=m;y++)
				{
					pls(t2[j][x+1][y],t1[j][x][y]*g2);
					pls(t2[j][x][y+1],t1[j][x][y]*g1);
					pls(t2[j][x][y],t1[j][x][y]);
					if(j)
					{
						pls(t1[j-1][x+1][y],t1[j][x][y]*g1);
						pls(t1[j-1][x][y+1],t1[j][x][y]*g2);
						pls(t1[j-1][x][y],t1[j][x][y]);
					}
				}
		}
	}
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n-i;j++) s[i][j]=t1[0][i][j]*fastpow(h[i][j][n-i-j],mod-2)%mod;
	ll inv=fastpow(3,mod-1-n)%mod;
	for(int i=0;i<=n;i++,printf("\n"))
		for(int j=0;j<=n-i;j++)
			printf("%lld ",s[i][j]*inv%mod*h[i][j][n-i-j]%mod);
}

Source code, Language: C++11

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5

Accepted

time: 0ms

memory: 5764kb

input:

output:

4860 14295 14526 4884 
14508 29202 14331 
14313 14529 
4873

result:

ok 10 numbers

Test #2:

score: 5

Accepted

time: 1ms

memory: 5828kb

input:

output:

339525305 585755378 185119564 514643854 627403284 752839711 
1818805 562123248 542722844 188321355 503033527 
706641173 41055444 221483535 311599235 
868980824 222671225 674863076 
7130996 919681572 
334277542

result:

ok 21 numbers

Test #3:

score: 5

Accepted

time: 0ms

memory: 5972kb

input:

output:

330670841 765934203 573230583 327599095 291643618 383155903 484592330 535807528 330670841 
674108488 172248481 127075963 547620411 538317547 794750014 172248481 731748168 
508087511 316342130 536206437 645955453 536206437 287881926 436690606 
383155903 637254059 123031804 123031804 758213062 3275990...

result:

ok 45 numbers

Test #4:

score: 5

Accepted

time: 2ms

memory: 6892kb

input:

output:

447548369 499314842 762933848 531327968 621357642 517525027 523218106 375080505 859922390 844409608 351337700 992204875 303050601 994785424 315924322 160905536 317796428 90377710 154013232 762945318 814834300 
917570800 171412181 464958514 311232845 871217848 51140059 54121620 557288439 934419604 85...

result:

ok 231 numbers

Test #5:

score: 5

Accepted

time: 2ms

memory: 6672kb

input:

17 500 999999993
9 5
3 4
16 0
2 9
0 3
0 10
10 2
8 9
2 4
7 4
16 1
3 1
7 4
7 3
6 11
6 11
5 12
2 1
1 5
15 2
3 7
1 7
8 5
6 5
12 4
2 11
6 11
0 11
2 1
14 3
4 8
1 1
12 0
12 4
17 0
5 0
4 0
7 0
8 7
3 6
4 0
8 1
10 6
4 13
5 9
1 6
1 11
2 1
5 3
5 4
0 1
6 9
6 5
1 13
4 2
8 2
1 0
0 8
4 8
16 0
1 7
0 6
11 6
13 4
9 1
...

output:

73713555 292019854 839027839 32264129 337043770 489124153 762794834 953369461 931933030 201311441 706033020 654720924 667837522 331629386 203866047 146428942 80087808 227951584 
107614386 675667983 422684032 430013546 794118469 532250461 480536934 172609641 77205950 581870046 349831672 9943099 80089...

result:

ok 171 numbers

Test #6:

score: 5

Accepted

time: 0ms

memory: 6864kb

input:

20 500 999999999290915342
6 2
3 1
3 17
4 16
2 2
16 3
15 1
18 2
0 20
12 0
17 2
14 2
10 5
3 15
7 4
14 6
20 0
0 17
3 2
4 3
5 1
10 2
2 0
10 5
4 12
2 3
0 20
4 4
8 4
9 1
7 13
6 10
9 3
4 11
6 11
14 4
9 8
17 3
8 3
0 3
10 5
3 2
6 5
8 3
3 7
12 6
13 3
0 20
0 20
3 11
5 13
6 14
8 8
16 4
14 0
4 0
16 4
12 5
1 3
6 ...

output:

347746568 870778417 397274503 837061945 446080085 363005104 172943807 551740479 656312788 201958492 726027566 88056681 668492087 529420087 533940215 602929657 295533841 535298438 884996458 216348826 212489223 
105354323 378705296 483680512 980143428 326305478 677037801 412107264 964228052 835458520 ...

result:

ok 231 numbers

Test #7:

score: 5

Accepted

time: 11ms

memory: 10440kb

input:

40 100000 20
39 0
28 0
16 0
2 0
23 0
2 0
26 0
3 0
40 0
27 0
20 0
28 0
4 0
11 0
35 0
15 0
24 0
11 0
18 0
27 0
11 0
37 0
29 0
6 0
34 0
13 0
29 0
27 0
39 0
16 0
15 0
32 0
6 0
39 0
2 0
23 0
2 0
20 0
2 0
33 0
4 0
23 0
10 0
28 0
32 0
13 0
15 0
3 0
18 0
31 0
25 0
14 0
27 0
39 0
4 0
25 0
21 0
22 0
18 0
13 0...

output:

294864057 921513962 837124343 690433846 952765059 812106511 127729056 661414358 381134557 208362653 324478173 757543566 373914546 672458698 24058063 203369653 40875666 271013891 155089053 764393367 766795271 564750055 508360475 903767717 65906070 759285636 440934457 413403579 519262773 561974337 345...

result:

ok 861 numbers

Test #8:

score: 5

Accepted

time: 14ms

memory: 10480kb

input:

40 100000 999999997
40 0
16 0
19 0
35 0
32 0
36 0
39 0
31 0
16 0
14 0
2 0
29 0
0 0
11 0
34 0
28 0
14 0
34 0
11 0
5 0
37 0
27 0
10 0
20 0
21 0
2 0
24 0
34 0
1 0
21 0
38 0
5 0
26 0
18 0
0 0
35 0
17 0
17 0
0 0
29 0
32 0
32 0
21 0
23 0
10 0
7 0
24 0
25 0
13 0
37 0
22 0
14 0
33 0
34 0
11 0
21 0
30 0
8 0
...

output:

894372889 878417001 506931167 328700088 221407291 653788742 886961707 331902828 912363850 492225334 809549304 653169038 829665664 241784230 635741006 8098640 302269907 430477549 417706919 94399480 746474400 807156500 663036735 708618616 276686759 241448097 849337757 817709992 460478396 559477628 464...

result:

ok 861 numbers

Test #9:

score: 5

Accepted

time: 12ms

memory: 12280kb

input:

50 50 999999994
24 5
12 33
15 1
18 29
15 0
3 21
1 43
36 7
18 17
30 7
4 7
14 35
4 6
36 5
32 2
36 0
16 28
2 18
44 6
12 36
17 22
5 44
15 33
19 2
36 6
47 1
3 6
15 6
15 14
17 19
3 17
35 15
40 5
10 26
4 31
15 8
25 4
13 30
13 36
30 20
13 2
1 23
24 0
8 25
4 26
11 27
47 2
14 22
10 21
25 16

output:

223307983 553978787 962532795 460235344 886369252 266289787 951915613 472315742 266624319 832861590 32411310 21639797 536401158 34530533 243389827 636728414 551847204 805086351 958619313 454615085 164858992 239573887 472912120 118112358 504991663 401529906 952021750 483757822 601132895 721995898 589...

result:

ok 1326 numbers

Test #10:

score: 5

Accepted

time: 16ms

memory: 10240kb

input:

40 100000 999999996
2 16
1 37
19 0
12 5
14 24
13 23
6 14
2 7
18 8
7 24
13 5
27 13
14 19
10 25
31 1
1 16
24 0
0 21
0 13
23 7
29 4
0 36
3 11
7 28
7 3
3 7
4 12
11 21
13 15
37 1
14 3
4 32
11 28
22 9
23 16
5 8
4 5
5 18
22 0
2 2
2 3
2 26
29 5
7 1
5 22
6 21
31 7
13 2
37 3
25 3
33 4
7 26
28 3
8 30
12 26
6 1...

output:

631518075 559538361 13218781 675542452 830609597 834071041 70189883 285880592 623564332 549426850 71833006 310576627 432993545 68547012 157784777 660894464 745131156 352461959 530756096 913689176 167683937 921169354 139379025 3425638 511348225 734959237 18710748 197478879 450746941 432985611 9208299...

result:

ok 861 numbers

Test #11:

score: 5

Accepted

time: 15ms

memory: 12088kb

input:

50 100000 999999999542416524
15 0
11 0
16 0
13 0
42 0
11 0
4 0
0 0
46 0
16 0
29 0
13 0
13 0
21 0
3 0
49 0
9 0
38 0
41 0
44 0
35 0
2 0
19 0
35 0
16 0
48 0
32 0
25 0
10 0
49 0
21 0
37 0
15 0
40 0
42 0
4 0
41 0
28 0
26 0
33 0
26 0
43 0
33 0
11 0
23 0
41 0
30 0
1 0
18 0
37 0
24 0
0 0
19 0
46 0
25 0
32 0...

output:

689812600 69472090 621264258 771650779 531227199 271097893 532691849 952571117 586295977 857802560 304749145 75289911 284425502 253956528 513830420 492228344 340700365 252810692 812612737 592748517 217149511 405117601 762752470 325589493 249220388 775677006 63598818 288345257 591725793 362747022 453...

result:

ok 1326 numbers

Test #12:

score: 5

Accepted

time: 14ms

memory: 12116kb

input:

50 100000 10
27 0
2 0
2 0
35 0
40 0
2 0
41 0
20 0
25 0
43 0
13 0
17 0
44 0
40 0
25 0
35 0
29 0
3 0
31 0
50 0
37 0
42 0
13 0
16 0
30 0
47 0
14 0
46 0
17 0
1 0
18 0
50 0
43 0
8 0
27 0
46 0
21 0
23 0
6 0
41 0
14 0
21 0
32 0
24 0
48 0
34 0
37 0
34 0
17 0
29 0
20 0
41 0
7 0
42 0
40 0
34 0
18 0
3 0
45 0
4...

output:

975135304 147851254 82162469 160833133 459908563 549113281 956374786 336024079 200440061 953563725 732970174 608496139 169133798 699242928 464434140 306029118 80549942 897601380 31136360 195349503 324363172 554749090 31769477 104906684 697169823 508441158 93384820 271746626 917879604 898396215 72445...

result:

ok 1326 numbers

Test #13:

score: 5

Accepted

time: 38ms

memory: 22384kb

input:

80 100000 100
60 15
38 20
11 44
36 28
8 53
34 42
41 26
2 18
13 16
41 17
3 4
21 41
46 11
44 8
18 46
5 37
0 51
4 59
53 21
34 1
15 10
23 56
23 26
11 18
13 43
23 46
23 20
3 43
4 51
5 22
46 32
17 16
18 23
41 39
39 28
53 27
67 11
22 14
4 6
69 3
7 65
6 13
31 29
30 22
0 58
63 17
32 11
51 22
3 60
17 55
18 29...

output:

158236349 542862024 298039431 314347331 108823255 970094636 549274320 626614923 514581687 762144846 900527988 151910521 821079709 720677693 53584501 900284410 386851762 405115456 763841364 250219020 426641030 449611995 719173053 442141689 621558753 517395366 455679890 516789822 833782516 725073093 5...

result:

ok 3321 numbers

Test #14:

score: 5

Accepted

time: 101ms

memory: 31792kb

input:

100 100000 100
65 15
56 30
41 25
37 39
35 26
44 37
6 35
0 48
5 48
48 14
7 26
27 51
9 25
4 79
1 92
24 48
16 30
2 66
13 6
24 43
2 30
59 28
5 71
51 9
87 0
46 10
23 32
6 54
67 5
48 1
4 2
67 5
50 39
9 70
23 62
37 0
48 49
20 9
24 36
47 47
29 16
36 25
34 21
16 27
77 14
54 8
27 54
31 42
19 2
25 4
49 45
17 8...

output:

472295183 346478816 602272032 239189054 53667022 532042245 283323590 47684495 177775868 454752604 496183046 441271359 354889968 530117901 886801844 739605049 979666370 391265964 256196546 317838988 927217501 940751022 568872254 276422169 260006754 47881644 401263131 406085363 858350255 933293832 498...

result:

ok 5151 numbers

Test #15:

score: 5

Accepted

time: 92ms

memory: 31768kb

input:

100 100 999999992
49 0
36 0
40 0
61 0
2 0
72 0
39 0
17 0
32 0
67 0
100 0
9 0
59 0
34 0
43 0
58 0
90 0
97 0
15 0
60 0
84 0
88 0
69 0
13 0
48 0
26 0
7 0
63 0
5 0
51 0
33 0
77 0
54 0
35 0
83 0
56 0
78 0
70 0
53 0
74 0
27 0
73 0
16 0
41 0
8 0
28 0
12 0
81 0
46 0
98 0
86 0
11 0
44 0
65 0
45 0
95 0
38 0
4...

output:

666608832 112748945 648446396 40878196 122466477 458985518 224858920 776932079 255872543 192720067 121247051 675176409 577430761 771102925 70150435 251202050 24351932 613787004 664235074 733924277 782682019 79462187 313865213 87526419 124630434 723318559 535656357 65874335 361549913 931304815 429387...

result:

ok 5151 numbers

Test #16:

score: 5

Accepted

time: 103ms

memory: 32356kb

input:

100 100000 999999998
8 34
17 3
39 48
72 20
35 51
38 6
57 5
30 41
7 72
18 32
27 17
0 76
74 20
97 2
26 6
5 81
36 9
52 37
64 21
35 38
5 26
9 7
49 34
9 2
15 35
34 47
1 90
58 41
5 67
32 0
9 24
82 14
39 36
35 8
2 96
60 15
25 57
0 37
20 45
52 1
25 27
12 77
16 10
49 5
25 20
29 64
74 16
33 41
16 18
18 22
45 ...

output:

574409859 420387344 803852712 250951711 709514820 698510862 305165635 12293623 933968286 44659908 728211036 139603261 261588127 688546296 707041787 30442459 93560544 813392337 36994764 609474201 358744533 557377002 509798391 480198065 324654278 77120124 199392087 114900941 889380068 659641933 592731...

result:

ok 5151 numbers

Test #17:

score: 5

Accepted

time: 102ms

memory: 30872kb

input:

100 100000 999999999869682971
65 18
4 93
36 37
57 30
12 36
55 23
38 35
26 18
30 8
9 12
3 48
3 71
34 2
49 36
42 49
45 11
3 81
40 14
23 53
44 18
16 72
60 11
31 59
9 12
54 43
73 6
48 14
55 8
55 1
29 29
13 51
23 58
6 93
21 4
49 6
60 30
10 65
51 48
82 4
5 64
8 60
53 28
71 8
83 6
24 53
3 73
61 18
11 54
75...

output:

714870555 924250733 743243186 618614568 233436229 726992 813961344 226465284 452044744 685851912 537923735 962745381 656081197 974530472 40032798 908076350 120792125 551670284 740500150 258515506 932898401 378568534 123741656 515989842 586687209 341461168 675981601 410107216 598106932 189325894 5613...

result:

ok 5151 numbers

Test #18:

score: 5

Accepted

time: 141ms

memory: 37948kb

input:

110 100000 999999999536785977
61 4
40 62
32 16
36 32
66 38
4 35
65 42
87 0
55 39
74 4
17 27
21 9
43 67
26 59
5 88
63 25
52 32
39 27
2 10
60 26
72 23
18 49
73 23
16 53
51 25
54 1
11 7
31 18
7 91
1 13
62 31
52 25
20 26
41 53
65 25
38 56
39 47
15 23
57 11
56 25
12 18
74 34
32 11
10 96
1 53
27 39
43 15
...

output:

690265524 424795579 418755336 548535634 675518358 644735219 391112650 326062268 623921376 14148311 433907617 284809105 701541068 88621257 371668355 655144335 743990593 265152521 529463566 61709326 414366843 978295547 484024264 509808894 12931508 970103942 840685174 105791691 390481160 16177557 29265...

result:

ok 6216 numbers

Test #19:

score: 5

Accepted

time: 154ms

memory: 38124kb

input:

110 100000 999999999495772595
84 1
83 25
42 3
53 14
48 45
42 2
25 79
96 11
21 74
29 59
67 42
56 11
72 36
73 24
49 30
28 24
17 34
59 42
3 50
70 32
54 44
31 41
33 26
47 21
22 39
5 23
28 38
52 52
6 49
95 10
48 14
58 39
11 90
17 8
36 63
21 30
10 92
20 69
62 43
2 88
17 78
50 11
75 17
19 51
34 55
32 58
46...

output:

880705160 603061327 71388893 911867702 96402358 558557295 4329135 203505985 956340749 506894709 63545119 58861669 693726265 382054292 417373379 102879963 514144115 612425052 847358839 961868787 662203573 693211221 641056521 151734861 175647639 447505064 517648134 635057128 67912059 662891163 5013193...

result:

ok 6216 numbers

Test #20:

score: 5

Accepted

time: 196ms

memory: 42236kb

input:

120 100000 999999999990988766
70 39
5 17
1 83
61 11
69 45
11 25
92 17
11 99
22 85
59 44
24 52
18 9
104 9
7 92
1 93
76 5
85 13
46 70
90 19
93 24
6 31
74 6
71 29
94 25
17 46
16 11
52 39
35 72
80 26
20 18
49 6
37 65
112 6
37 41
19 26
14 30
1 0
60 33
11 98
16 7
64 23
73 47
22 5
62 12
51 8
8 46
30 81
30 ...

output:

59622287 95241512 471648342 753472650 822585424 183560420 32479299 341147199 827766260 191487139 112776759 679192955 760836123 864540815 893634246 115848104 536304465 217083442 295096504 535118131 592816890 41162870 638449366 228716106 285071270 487393637 475126240 773066233 401497173 146495807 2924...

result:

ok 7381 numbers