QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#49400#4690. 社交网络yukino_yukinoshita100 ✓19ms3972kbC++1.2kb2022-09-20 22:32:322022-09-20 22:32:34

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-20 22:32:34]
  • 评测
  • 测评结果：100
  • 用时：19ms
  • 内存：3972kb
查看
  • [2022-09-20 22:32:32]
  • 提交

answer

#include <bits/stdc++.h>
#define FOR(i,j,k) for(int i=j; i<=k; ++i)
#define ROF(i,j,k) for(int i=j; i>=k; --i)
inline int read (void) {
  int x = 0, f = 1, ch = getchar();
  while(!isdigit(ch)) { if(ch == '-') f = -f; ch = getchar(); }
  while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
  return x * f;
}
const int maxn = 255;
const int mod = 10007;
inline int ksm (int a, int b) {
  int c = 1;
  while(b) {
    if(b&1) c = 1ll * c * a % mod;
    a = 1ll * a * a % mod; b >>= 1;
  } return c;
}
int a[maxn][maxn];
inline int det (int n) {
  int ans = 1;
  FOR(i,2,n) {
    int pos = 0;
    FOR(j,i,n) if(a[j][i]) { pos = j; break; }
    if(!pos) return 0;
    if(pos > i) std::swap (a[i], a[pos]), ans = (mod - ans) % mod;
    ans = 1ll * ans * a[i][i] % mod;
    int inv = ksm (a[i][i], mod-2);
    FOR(j,i,n) a[i][j] = 1ll * a[i][j] * inv % mod;
    FOR(j,i+1,n) if(a[j][i]) ROF(k,n,i)
      a[j][k] = (a[j][k] - 1ll * a[j][i] * a[i][k] % mod + mod) % mod;
  } return ans;
}
int main (void) {
  int n = read(), m = read();
  FOR(i,1,m) {
    int v = read(), u = read();
    if(u == v) continue;
    a[u][v] = (a[u][v] + mod - 1) % mod;
    a[v][v] = (a[v][v] + 1) % mod;
  }
  printf("%d\n", det (n));
  return 0;
}
Source code, Language: C++

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5
Accepted
time: 2ms
memory: 3692kb

input:

9
10
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
4 3
4 2

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 5
Accepted
time: 2ms
memory: 3620kb

input:

10
80
5 10
1 8
7 8
6 2
5 7
9 2
4 7
3 7
1 6
3 10
7 9
8 4
7 1
5 2
1 7
4 2
8 3
8 1
3 9
8 2
2 10
4 3
9 10
5 3
3 8
3 4
6 10
4 8
4 5
5 8
9 5
9 6
10 2
10 5
6 1
2 1
9 4
7 10
5 6
10 7
10 8
5 9
9 7
9 8
4 10
8 9
7 2
2 7
10 1
7 3
6 8
7 6
9 1
6 5
2 4
6 3
2 9
8 10
10 9
8 5
4 1
6 9
2 3
1 3
1 9
5 4
1 5
5 1
10 4
10 ...

output:

9796

result:

ok 1 number(s): "9796"

Test #3:

score: 5
Accepted
time: 1ms
memory: 3688kb

input:

10
74
5 10
1 8
7 8
6 2
5 7
9 2
4 7
3 7
1 6
3 10
7 9
8 4
7 1
5 2
1 7
4 2
8 3
8 1
3 9
8 2
2 10
4 3
9 10
5 3
3 8
3 4
6 10
4 8
4 5
5 8
9 5
9 6
10 2
10 5
6 1
2 1
9 4
7 10
5 6
10 7
10 8
5 9
9 7
9 8
4 10
8 9
7 2
2 7
10 1
7 3
6 8
7 6
9 1
6 5
2 4
6 3
2 9
8 10
10 9
8 5
4 1
6 9
2 3
1 3
1 9
5 4
1 5
5 1
10 4
10 ...

output:

9712

result:

ok 1 number(s): "9712"

Test #4:

score: 5
Accepted
time: 2ms
memory: 3732kb

input:

10
82
5 10
1 8
7 8
6 2
5 7
9 2
4 7
3 7
1 6
3 10
7 9
8 4
7 1
5 2
1 7
4 2
8 3
8 1
3 9
8 2
2 10
4 3
9 10
5 3
3 8
3 4
6 10
4 8
4 5
5 8
9 5
9 6
10 2
10 5
6 1
2 1
9 4
7 10
5 6
10 7
10 8
5 9
9 7
9 8
4 10
8 9
7 2
2 7
10 1
7 3
6 8
7 6
9 1
6 5
2 4
6 3
2 9
8 10
10 9
8 5
4 1
6 9
2 3
1 3
1 9
5 4
1 5
5 1
10 4
10 ...

output:

2238

result:

ok 1 number(s): "2238"

Test #5:

score: 5
Accepted
time: 0ms
memory: 3712kb

input:

10
86
5 10
1 8
7 8
6 2
5 7
9 2
4 7
3 7
1 6
3 10
7 9
8 4
7 1
5 2
1 7
4 2
8 3
8 1
3 9
8 2
2 10
4 3
9 10
5 3
3 8
3 4
6 10
4 8
4 5
5 8
9 5
9 6
10 2
10 5
6 1
2 1
9 4
7 10
5 6
10 7
10 8
5 9
9 7
9 8
4 10
8 9
7 2
2 7
10 1
7 3
6 8
7 6
9 1
6 5
2 4
6 3
2 9
8 10
10 9
8 5
4 1
6 9
2 3
1 3
1 9
5 4
1 5
5 1
10 4
10 ...

output:

9012

result:

ok 1 number(s): "9012"

Test #6:

score: 5
Accepted
time: 2ms
memory: 3640kb

input:

10
87
5 10
1 8
7 8
6 2
5 7
9 2
4 7
3 7
1 6
3 10
7 9
8 4
7 1
5 2
1 7
4 2
8 3
8 1
3 9
8 2
2 10
4 3
9 10
5 3
3 8
3 4
6 10
4 8
4 5
5 8
9 5
9 6
10 2
10 5
6 1
2 1
9 4
7 10
5 6
10 7
10 8
5 9
9 7
9 8
4 10
8 9
7 2
2 7
10 1
7 3
6 8
7 6
9 1
6 5
2 4
6 3
2 9
8 10
10 9
8 5
4 1
6 9
2 3
1 3
1 9
5 4
1 5
5 1
10 4
10 ...

output:

3342

result:

ok 1 number(s): "3342"

Test #7:

score: 5
Accepted
time: 3ms
memory: 3744kb

input:

100
9000
81 7
82 40
1 9
31 37
24 76
99 69
34 95
60 27
70 85
54 44
55 59
13 28
4 28
95 94
100 24
53 12
81 93
32 71
96 4
21 96
66 92
54 69
31 41
25 89
82 18
34 17
100 97
10 34
26 56
53 40
59 12
5 87
39 61
24 44
100 14
94 63
25 55
92 89
56 71
86 18
16 54
88 78
2 99
26 99
81 43
2 77
35 50
34 84
9 29
44 ...

output:

5012

result:

ok 1 number(s): "5012"

Test #8:

score: 5
Accepted
time: 4ms
memory: 3776kb

input:

100
9200
81 7
82 40
1 9
31 37
24 76
99 69
34 95
60 27
70 85
54 44
55 59
13 28
4 28
95 94
100 24
53 12
81 93
32 71
96 4
21 96
66 92
54 69
31 41
25 89
82 18
34 17
100 97
10 34
26 56
53 40
59 12
5 87
39 61
24 44
100 14
94 63
25 55
92 89
56 71
86 18
16 54
88 78
2 99
26 99
81 43
2 77
35 50
34 84
9 29
44 ...

output:

310

result:

ok 1 number(s): "310"

Test #9:

score: 5
Accepted
time: 5ms
memory: 3756kb

input:

150
9200
102 149
54 31
55 14
92 57
97 4
1 12
83 46
131 24
16 122
66 91
71 17
133 82
74 120
40 64
146 75
37 46
119 22
3 32
35 98
73 134
80 119
54 121
73 11
22 16
64 28
14 145
44 126
146 100
131 30
17 87
54 147
23 12
117 29
18 2
77 51
81 1
35 130
39 100
101 57
114 37
26 106
126 87
79 132
17 54
88 12
1...

output:

3466

result:

ok 1 number(s): "3466"

Test #10:

score: 5
Accepted
time: 6ms
memory: 3776kb

input:

150
19200
102 149
54 31
55 14
92 57
97 4
1 12
83 46
131 24
16 122
66 91
71 17
133 82
74 120
40 64
146 75
37 46
119 22
3 32
35 98
73 134
80 119
54 121
73 11
22 16
64 28
14 145
44 126
146 100
131 30
17 87
54 147
23 12
117 29
18 2
77 51
81 1
35 130
39 100
101 57
114 37
26 106
126 87
79 132
17 54
88 12
...

output:

4323

result:

ok 1 number(s): "4323"

Test #11:

score: 5
Accepted
time: 3ms
memory: 3864kb

input:

150
19204
102 149
54 31
55 14
92 57
97 4
1 12
83 46
131 24
16 122
66 91
71 17
133 82
74 120
40 64
146 75
37 46
119 22
3 32
35 98
73 134
80 119
54 121
73 11
22 16
64 28
14 145
44 126
146 100
131 30
17 87
54 147
23 12
117 29
18 2
77 51
81 1
35 130
39 100
101 57
114 37
26 106
126 87
79 132
17 54
88 12
...

output:

3133

result:

ok 1 number(s): "3133"

Test #12:

score: 5
Accepted
time: 7ms
memory: 3808kb

input:

166
25204
93 17
49 8
49 141
83 87
87 119
1 12
75 54
118 89
15 47
163 3
60 41
64 53
120 116
67 108
36 101
142 41
132 67
33 132
107 117
3 1
157 51
159 146
32 53
66 141
73 13
49 102
66 18
20 14
58 14
13 106
40 102
132 94
118 99
15 165
49 128
20 160
160 57
105 159
16 66
69 161
73 46
32 86
35 157
91 113
...

output:

8761

result:

ok 1 number(s): "8761"

Test #13:

score: 5
Accepted
time: 11ms
memory: 3908kb

input:

240
55204
201 165
171 66
34 174
57 233
197 233
1 12
189 100
82 35
10 206
112 205
179 2
181 197
220 178
118 50
129 160
47 5
25 142
235 150
91 175
160 181
211 186
2 95
159 174
183 135
50 183
34 135
183 13
135 144
151 68
131 58
177 125
146 201
28 86
228 226
82 47
11 87
171 188
14 190
111 4
210 137
148 ...

output:

1023

result:

ok 1 number(s): "1023"

Test #14:

score: 5
Accepted
time: 17ms
memory: 3872kb

input:

245
55204
197 141
167 193
34 8
56 197
193 229
1 12
185 136
80 119
10 161
110 138
175 88
178 28
216 59
115 198
127 7
46 19
25 21
230 200
89 213
157 117
207 112
2 90
241 1
242 182
156 117
179 204
49 184
33 216
179 81
132 208
148 52
128 143
173 224
143 210
27 197
224 69
80 133
11 39
168 71
14 127
108 1...

output:

3382

result:

ok 1 number(s): "3382"

Test #15:

score: 5
Accepted
time: 19ms
memory: 3964kb

input:

250
62000
193 157
164 109
33 93
55 171
190 15
1 12
181 213
78 222
10 116
108 90
171 215
174 139
211 230
113 126
124 125
45 43
24 151
247 37
226 52
88 22
154 85
203 79
2 86
236 47
237 223
153 90
176 61
48 194
33 57
175 189
130 51
145 65
126 6
170 111
140 248
27 68
219 200
78 237
10 239
164 234
14 63
...

output:

3755

result:

ok 1 number(s): "3755"

Test #16:

score: 5
Accepted
time: 19ms
memory: 3864kb

input:

250
62002
84 210
219 137
78 112
139 13
115 35
25 174
164 41
199 144
5 230
58 98
113 7
38 230
94 236
215 83
215 9
4 11
206 29
193 245
166 59
160 183
245 241
205 71
163 95
198 184
105 57
29 185
81 228
116 7
120 180
42 71
15 43
234 139
121 232
193 43
142 87
239 109
181 69
92 104
35 187
76 39
38 147
133...

output:

9095

result:

ok 1 number(s): "9095"

Test #17:

score: 5
Accepted
time: 14ms
memory: 3972kb

input:

250
62202
139 29
236 147
12 6
96 202
55 189
213 218
67 111
25 168
179 46
114 107
223 77
174 116
193 52
58 134
132 55
124 150
141 96
148 185
16 74
237 94
5 27
100 182
99 18
114 220
32 55
117 24
37 172
65 154
161 189
42 159
57 22
141 36
249 104
188 173
197 174
166 107
167 26
148 106
228 161
121 46
190...

output:

3835

result:

ok 1 number(s): "3835"

Test #18:

score: 5
Accepted
time: 15ms
memory: 3932kb

input:

250
62212
218 213
227 166
102 123
97 221
60 99
45 227
135 175
222 244
18 173
72 9
237 153
212 174
77 174
107 98
193 42
194 161
98 211
237 210
153 179
106 15
208 15
210 198
234 81
231 50
107 198
98 51
245 90
114 234
210 87
163 240
74 112
28 57
146 224
143 102
145 133
181 91
95 26
86 105
173 45
42 213...

output:

2583

result:

ok 1 number(s): "2583"

Test #19:

score: 5
Accepted
time: 11ms
memory: 3876kb

input:

250
62233
195 155
150 227
96 66
143 238
84 67
248 239
16 233
242 41
195 51
243 221
117 186
234 199
142 198
57 230
138 240
231 15
50 172
118 226
105 37
17 232
128 192
84 94
120 173
38 79
37 92
67 114
179 20
75 100
78 32
197 49
191 54
57 210
206 222
185 145
107 237
92 201
202 21
18 171
16 245
208 179
...

output:

9587

result:

ok 1 number(s): "9587"

Test #20:

score: 5
Accepted
time: 19ms
memory: 3864kb

input:

250
62247
156 102
120 210
222 132
164 226
40 41
219 128
208 210
153 245
161 245
96 169
26 34
3 158
35 52
243 102
141 129
243 39
180 165
247 78
67 21
37 136
170 210
133 183
207 31
37 28
9 125
157 203
130 122
181 98
57 184
169 235
230 195
66 210
74 16
195 33
233 135
108 62
18 172
41 151
97 23
91 16
10...

output:

63

result:

ok 1 number(s): "63"
English 繁體中文 简体中文

Server Time: 2024-12-02 07:24:04 | OpenSource Project