QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#296984	#4916. 抽奖机	MEKHANE	0	0ms	0kb	C++17	1.7kb	2024-01-03 20:49:13	2024-01-03 20:49:14

Judging History

This is the latest submission verdict.

[2024-01-03 20:49:14]
Judged

Verdict: 0
Time: 0ms
Memory: 0kb

Show

[2024-01-03 20:49:13]
Submitted

answer

#pragma GCC optimize(3,"inline","Ofast")
#include<bits/stdc++.h>
#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,f[N][N],g[N][N],v1[N][N],v2[N][N],jc[N],inv[N];
long long k;
int ksm(int x,int k){
    int res=1;
    for(;k;k/=2,x=1ll*x*x%mod) if(k&1) res=1ll*res*x%mod;
    return res;
}
void mul(int n,int a[][N],int x,int y){per(i,n-1,0) per(j,n-i-1,0) a[i+1][j]=(a[i+1][j]+1ll*a[i][j]*x)%mod,a[i][j+1]=(a[i][j+1]+1ll*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-i-1) a[i+1][j]=(a[i+1][j]-1ll*a[i][j]*x%mod+mod)%mod,a[i][j+1]=(a[i][j+1]-1ll*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+1ll*v2[o1][o2]*a[o1][o2])%mod;
            b[i][l]=dq,div(n,v2,1,1),mul(n,v2,y,x);
        }div(n,v1,1,1),mul(n,v1,x,y);
    }
}
signed main(){
    freopen("machine.in","r",stdin);
    freopen("machine.out","w",stdout);
    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]=1ll*jc[i-1]*i%mod;
    inv[n]=ksm(jc[n],mod-2);
    per(i,n-1,1) inv[i]=1ll*inv[i+1]*(i+1)%mod;
    int xs=ksm(3,mod-1-n);
    rep(i,0,n){rep(j,0,n-i) cout<<1ll*f[i][j]*jc[n]%mod*inv[i]%mod*inv[j]%mod*inv[n-i-j]%mod*xs%mod<<' '; cout<<'\n';}
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0

Dangerous Syscalls

input:

output:

result:

Test #2:

score: 0

Dangerous Syscalls

input:

output:

result:

Test #3:

score: 0

Dangerous Syscalls

input:

output:

result:

Test #4:

score: 0

Dangerous Syscalls

input:

output:

result:

Test #5:

score: 0

Dangerous Syscalls

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:

result:

Test #6:

score: 0

Dangerous Syscalls

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:

result:

Test #7:

score: 0

Dangerous Syscalls

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:

result:

Test #8:

score: 0

Dangerous Syscalls

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:

result:

Test #9:

score: 0

Dangerous Syscalls

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:

result:

Test #10:

score: 0

Dangerous Syscalls

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:

result:

Test #11:

score: 0

Dangerous Syscalls

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:

result:

Test #12:

score: 0

Dangerous Syscalls

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:

result:

Test #13:

score: 0

Dangerous Syscalls

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:

result:

Test #14:

score: 0

Dangerous Syscalls

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:

result:

Test #15:

score: 0

Dangerous Syscalls

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:

result:

Test #16:

score: 0

Dangerous Syscalls

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:

result:

Test #17:

score: 0

Dangerous Syscalls

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:

result:

Test #18:

score: 0

Dangerous Syscalls

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:

result:

Test #19:

score: 0

Dangerous Syscalls

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:

result:

Test #20:

score: 0

Dangerous Syscalls

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 ...