QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#296978	#4916. 抽奖机	MEKHANE	0	1815ms	4040kb	C++17	1.6kb	2024-01-03 20:43:54	2024-01-03 20:43:54

Judging History

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

[2024-01-03 20:43:54]
评测

测评结果：0
用时：1815ms
内存：4040kb

查看

[2024-01-03 20:43:54]
提交

answer

#include<bits/stdc++.h>
#define int long long
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define per(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
const int N=125,mod=1e9+9,w=115381398,iw=884618610;
int n,m,k,f[N][N],g[N][N],v1[N][N],v2[N][N],jc[N],inv[N];
int ksm(int x,int k){
    int res=1;
    for(;k;k/=2,x=x*x%mod) if(k&1) res=res*x%mod;
    return res;
}
void mul(int n,int a[][N],int x,int y){per(i,n-1,0) per(j,n-1,0) a[i+1][j]=(a[i+1][j]+a[i][j]*x)%mod,a[i][j+1]=(a[i][j+1]+a[i][j]*y)%mod;}
void div(int n,int a[][N],int x,int y){rep(i,0,n-1) rep(j,0,n-1) a[i+1][j]=(a[i+1][j]-a[i][j]*x%mod+mod)%mod,a[i][j+1]=(a[i][j+1]-a[i][j]*y%mod+mod)%mod;}
void dft(int n,int a[][N],int b[][N],int x,int y){
    rep(i,0,n) rep(j,0,n-i) b[i][j]=v1[i][j]=0;
    v1[0][0]=1;
    rep(i,1,n) mul(n,v1,1,1);
    rep(i,0,n){
        rep(j,0,n) rep(k,0,n-j) v2[j][k]=v1[j][k];
        rep(l,0,n-i){
            int dq=0;
            rep(o1,0,n) rep(o2,0,n-o1) dq=(dq+v2[o1][o2]*a[o1][o2])%mod;
            b[i][l]=dq,div(n,v2,1,1),mul(n,v2,iw,w);
        }div(n,v1,1,1),mul(n,v1,w,iw);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    rep(i,1,m){int a,b; cin>>a>>b,f[a][b]++;}
    dft(n,f,g,w,iw);
    rep(i,0,n) rep(j,0,n-i) g[i][j]=ksm(g[i][j],k%(mod-1));
    dft(n,g,f,iw,w),jc[0]=inv[0]=1;
    rep(i,1,n) jc[i]=jc[i-1]*i%mod;
    inv[n]=ksm(jc[n],mod-2);
    per(i,n-1,1) inv[i]=inv[i+1]*(i+1)%mod;
    int xs=ksm(3,mod-1-n);
    rep(i,0,n){rep(j,0,n-i) cout<<f[i][j]*jc[n]%mod*inv[i]%mod*inv[j]%mod*inv[n-i-j]%mod*xs%mod<<' '; cout<<'\n';}
}

源文件, 语言: C++17

详细

Test #1:

score: 0

Wrong Answer

time: 1ms

memory: 3636kb

input:

output:

4860 14508 14313 4873 
14295 29202 14529 
14526 14331 
4884

result:

wrong answer 2nd numbers differ - expected: '14295', found: '14508'

Test #2:

score: 0

Wrong Answer

time: 0ms

memory: 3648kb

input:

output:

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

result:

wrong answer 2nd numbers differ - expected: '585755378', found: '1818805'

Test #3:

score: 0

Wrong Answer

time: 1ms

memory: 3504kb

input:

output:

330670841 674108488 508087511 383155903 798206816 605060678 573230583 731748168 696724530 
765934203 172248481 316342130 637254059 547620411 287881926 774960768 674108488 
573230583 127075963 536206437 123031804 204396258 316342130 484592330 
327599095 547620411 645955453 123031804 538317547 4189900...

result:

wrong answer 2nd numbers differ - expected: '765934203', found: '674108488'

Test #4:

score: 0

Wrong Answer

time: 3ms

memory: 3500kb

input:

output:

447548369 917570800 382961459 498522848 333611143 614127517 47513805 511291577 259283044 1860685 120172549 836910339 607132969 735077256 120643976 978840577 220804109 428610763 233418397 382589448 331353857 
499314842 171412181 899375875 51175244 845418216 818737615 515057433 90294039 931149458 6039...

result:

wrong answer 2nd numbers differ - expected: '499314842', found: '917570800'

Test #5:

score: 0

Wrong Answer

time: 2ms

memory: 3664kb

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 107614386 886855068 854918912 945431070 224654916 217899953 295274892 574794803 817275221 687860385 849779645 525181068 839048174 312104046 747788622 32845476 827416945 
292019854 675667983 818219810 352221523 540826123 164388653 345424201 215542085 63897197 941667434 23807424 843572027 409...

result:

wrong answer 2nd numbers differ - expected: '292019854', found: '107614386'

Test #6:

score: 0

Wrong Answer

time: 0ms

memory: 3728kb

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 105354323 181002147 417152228 114245129 588976549 180578468 662861777 580028176 189836377 914683160 282178067 895366243 991485778 907172079 67431859 520597687 285342115 265813646 972894866 990311524 
870778417 378705296 365329303 53385902 584995897 259074028 599068651 433524301 714528307 6...

result:

wrong answer 2nd numbers differ - expected: '870778417', found: '105354323'

Test #7:

score: 0

Wrong Answer

time: 41ms

memory: 3624kb

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 495116875 720340606 375426231 136620506 746536498 650081740 655686013 460987975 676779056 510665285 77318063 90679259 127156607 48051165 157754086 688211088 496096773 736584598 409134328 212289716 766085272 167872555 16207352 282389154 478248941 367512046 172589940 894591595 812147203 8162...

result:

wrong answer 2nd numbers differ - expected: '921513962', found: '495116875'

Test #8:

score: 0

Wrong Answer

time: 41ms

memory: 3572kb

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 603156091 248570532 203502432 720488173 807052948 924004143 433183829 861995164 931027354 282533635 495823099 515106282 975768435 739440657 338804149 663931352 253300770 377400728 295764862 431552155 350598166 644322029 619227803 19224773 471093193 870046040 291192012 806122449 977933909 3...

result:

wrong answer 2nd numbers differ - expected: '878417001', found: '603156091'

Test #9:

score: 0

Wrong Answer

time: 82ms

memory: 3664kb

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 954407174 186103075 27439291 321252016 867999494 508827517 979531179 846286865 197183563 126298753 970272251 206919503 472129247 965775284 504494242 221428403 574829877 738633543 52133456 193848598 909248921 151233826 982092008 664331403 801996181 383277689 280235282 584235705 520080059 17...

result:

wrong answer 2nd numbers differ - expected: '553978787', found: '954407174'

Test #10:

score: 0

Wrong Answer

time: 42ms

memory: 3800kb

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 915616103 736400346 322191069 492488984 148170208 853383071 810485572 602749484 930512273 61119738 215585847 328447144 174522815 378308499 406450864 612392511 829477264 803449525 285637139 693305362 115266532 887230388 174509718 723917918 587021729 418328784 185271739 817726219 290039787 7...

result:

wrong answer 2nd numbers differ - expected: '559538361', found: '915616103'

Test #11:

score: 0

Wrong Answer

time: 88ms

memory: 3668kb

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 895022729 740922203 562906368 569244504 374006763 272832900 144106241 867454832 213833666 979537624 899846754 465414213 371168099 952728537 46051740 417397458 444859663 127583198 124218501 646787413 232048906 823662618 121305917 910540916 485900909 763267018 73631977 501246291 112069556 82...

result:

wrong answer 2nd numbers differ - expected: '69472090', found: '895022729'

Test #12:

score: 0

Wrong Answer

time: 84ms

memory: 3832kb

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 96883735 515019801 284469386 896996503 844903308 844143958 291421175 701905670 830976600 632649439 373743021 537054972 917999143 151126063 800931696 337610302 560146997 40321739 947576727 278788568 387983052 897609876 120707671 928697987 242234244 151284436 275205953 344079951 927127618 42...

result:

wrong answer 2nd numbers differ - expected: '147851254', found: '96883735'

Test #13:

score: 0

Wrong Answer

time: 519ms

memory: 3788kb

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 191943034 330401983 26344820 595733556 839111914 190718187 948212654 386397760 828344663 184111549 622814221 286067130 412719044 663249115 426158704 877323910 115106498 116399993 509419068 490234142 754056031 991461637 582651759 705212084 945977350 716086651 125895015 962609636 479444681 3...

result:

wrong answer 2nd numbers differ - expected: '542862024', found: '191943034'

Test #14:

score: 0

Wrong Answer

time: 1241ms

memory: 3916kb

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 295667606 27182941 493936152 233281090 372673287 138190970 379391667 477794256 15351799 929073036 306830743 429571406 962566983 611227704 339672812 124597858 291647478 268376804 323640430 81849309 669238278 175491346 489799880 792920023 131887017 67365614 930154711 767724831 241460159 5017...

result:

wrong answer 2nd numbers differ - expected: '346478816', found: '295667606'

Test #15:

score: 0

Wrong Answer

time: 1232ms

memory: 4040kb

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 705697611 469858622 300752170 840135161 270960287 191818402 294474264 738307598 934942327 459776161 953382015 373979789 311816223 416360071 610156018 824126498 322198555 976136001 425020470 885100524 339722792 497813505 884754674 21197050 903583502 866618455 575525382 999562747 720511885 9...

result:

wrong answer 2nd numbers differ - expected: '112748945', found: '705697611'

Test #16:

score: 0

Wrong Answer

time: 1249ms

memory: 3816kb

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 692579267 239507537 660442426 486657511 884976774 579690859 922819962 28282960 528167251 579447728 190474891 387331144 977658159 768688886 609479974 5049171 2994535 525312502 620746769 321570065 1482971 937978688 906107571 512527517 268219800 972069776 640253996 453445743 232781544 1493046...

result:

wrong answer 2nd numbers differ - expected: '420387344', found: '692579267'

Test #17:

score: 0

Wrong Answer

time: 1244ms

memory: 4040kb

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 112093936 28199072 964370949 186541523 248115932 955539006 170432410 65199964 614724822 215559267 444347168 105676310 957812466 955493522 8447573 905419406 974156755 660582174 791045341 522204303 767896193 339641961 187340607 98748235 105633529 846329501 938527036 50901260 418937987 279260...

result:

wrong answer 2nd numbers differ - expected: '924250733', found: '112093936'

Test #18:

score: 0

Wrong Answer

time: 1812ms

memory: 3904kb

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 7334538 496241714 283538099 744091107 128418695 865894706 125933308 186449409 645845237 763449274 993294095 51674539 867658982 967880174 164299108 244794414 852706873 919750301 966079746 984989265 819851537 81067968 914537950 475187721 827397484 842815498 578283196 686200281 45002085 90414...

result:

wrong answer 2nd numbers differ - expected: '424795579', found: '7334538'

Test #19:

score: 0

Wrong Answer

time: 1815ms

memory: 3900kb

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 773180587 503362407 246126133 80657453 397503861 778035413 837737917 695432095 544552682 796011307 76742152 995220095 243486286 628431177 483521612 318408309 967479981 663121619 163815442 308984174 106203070 92228783 671064542 744044894 648841842 193493132 341966927 686069479 422231986 351...

result:

wrong answer 2nd numbers differ - expected: '603061327', found: '773180587'

Test #20:

score: 0

Time Limit Exceeded

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 900905059 878633879 540385067 758892605 819610017 917915178 564619288 231180669 714421020 421615523 85439652 782083296 900223786 558509858 462415571 124253824 274925716 703806195 628399735 519783060 338316062 653090808 555304193 264905108 243544029 910098952 951100129 794641614 764778311 16...