QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #830221 | #9910. 颠倒歌 | hhoppitree# | 34 | 106ms | 22876kb | C++14 | 2.6kb | 2024-12-24 17:04:39 | 2024-12-24 17:04:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 5005, P = 998244353;
int f(int x) {
int res = 1;
for (int i = 1; i <= x - 2; ++i) res = 1ll * res * x % P;
return res;
}
vector<int> G[N];
unsigned int hs[N];
vector<int> ch;
int cs[N][N];
void dfs(int x, int y, int st, unsigned int val) {
ch.push_back(x);
if (G[x].size() != 2) {
} else {
for (auto v : G[x]) {
if (v != y) dfs(v, x, st, val);
}
}
}
int res = 1, vis[N], C;
void Dfs(int x) {
++C, vis[x] = 1;
for (auto v : G[x]) if (!vis[v]) Dfs(v);
}
pair<int, int> fa[N][N];
int siz[N][N];
pair<int, int> find(int x, int y) {
return fa[x][y].first == x && fa[x][y].second == y ? fa[x][y] : fa[x][y] = find(fa[x][y].first, fa[x][y].second);
}
signed main() {
int ty, k, n; scanf("%d%d%d", &ty, &k, &n);
mt19937 rnd;
for (int j = 1; j <= k; ++j) {
for (int l = 1; l <= n; ++l) G[l].clear();
for (int i = 1, x, y; i < n; ++i) {
scanf("%d%d", &x, &y), G[x].push_back(y), G[y].push_back(x);
}
for (int i = 1; i <= n; ++i) {
for (auto v : G[i]) {
if (G[i].size() != 2) {
ch = {i}, dfs(v, i, i, rnd());
for (auto v1 : ch) {
for (auto v2 : ch) {
++cs[v1][v2];
}
}
}
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
fa[i][j] = make_pair(i, j), siz[i][j] = 1;
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int l = 1; l <= n; ++l) {
if (i == j || j == l) continue;
if (cs[i][j] == k * 2 && cs[j][l] == k * 2 && cs[i][l] == k * 2) {
pair<int, int> ta = find(i, j), tb = find(j, l);
if (ta != tb) {
fa[ta.first][ta.second] = tb;
siz[tb.first][tb.second] += siz[ta.first][ta.second];
}
}
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i == j) continue;
if (find(i, j).first == i && find(i, j).second == j && siz[i][j] != 1) {
int V = 1;
while (V * (V - 1) != siz[i][j]) ++V;
res = 1ll * res * f(V) % P;
}
}
}
printf("%d\n", res);
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 10
Accepted
time: 1ms
memory: 8016kb
input:
1 4 7 1 7 4 1 2 3 2 6 5 4 7 2 5 7 7 3 1 2 4 1 4 3 5 6 5 4 2 4 3 5 7 2 2 6 1 7 1 7 6 4 5 2 3 6 3 1 4 5
output:
9
result:
ok single line: '9'
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 10176kb
input:
0 3 6 6 4 1 3 4 1 5 2 4 5 6 4 3 1 2 5 3 4 5 4 4 1 3 1 5 2 5 4 6 4
output:
9
result:
wrong answer 1st lines differ - expected: '2', found: '9'
Subtask #2:
score: 0
Wrong Answer
Test #5:
score: 0
Wrong Answer
time: 4ms
memory: 22532kb
input:
0 1 189 77 175 145 175 4 175 92 175 175 33 175 125 175 185 157 175 186 175 115 175 113 175 38 175 175 138 175 133 175 48 175 128 175 66 175 34 175 148 150 175 175 104 175 84 175 59 175 154 80 175 176 175 135 175 55 175 139 175 175 132 175 91 13 175 175 110 155 175 175 60 175 184 73 175 152 175 83 17...
output:
1
result:
wrong answer 1st lines differ - expected: '5245226', found: '1'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 7
Accepted
Test #25:
score: 7
Accepted
time: 52ms
memory: 20768kb
input:
1 1 156 69 74 65 126 110 16 134 129 3 22 78 5 140 23 53 138 109 67 82 74 42 57 23 143 12 112 7 13 154 105 100 118 63 28 41 37 145 25 80 142 111 148 81 85 133 13 104 89 83 14 39 24 120 97 98 131 94 55 107 91 38 130 122 36 2 32 82 94 35 49 40 108 68 146 101 130 101 76 105 58 80 137 152 87 78 66 32 55 ...
output:
261947439
result:
ok single line: '261947439'
Test #26:
score: 7
Accepted
time: 64ms
memory: 20636kb
input:
1 1 168 140 135 69 51 33 66 138 48 168 90 102 43 137 98 117 21 88 131 29 14 117 157 77 78 85 88 119 32 114 68 55 67 160 166 12 149 155 85 20 113 132 149 131 19 97 139 22 78 16 157 151 143 99 156 159 71 72 119 161 163 68 28 101 89 27 133 96 146 125 44 151 24 14 114 116 111 89 25 115 138 46 1 51 47 40...
output:
260505142
result:
ok single line: '260505142'
Test #27:
score: 7
Accepted
time: 51ms
memory: 20648kb
input:
1 1 155 77 28 89 81 138 11 85 7 124 53 29 52 116 32 151 66 103 80 145 77 82 51 116 138 141 144 57 20 34 101 14 84 75 68 42 64 95 117 117 137 122 33 76 50 12 71 112 44 134 83 134 18 105 10 75 122 106 94 84 69 1 123 140 10 70 71 78 133 24 152 87 13 9 31 135 142 101 146 149 129 28 16 52 39 26 119 146 3...
output:
252700555
result:
ok single line: '252700555'
Test #28:
score: 7
Accepted
time: 106ms
memory: 22664kb
input:
1 1 200 24 110 97 182 163 183 115 67 21 193 168 118 88 19 10 150 33 76 15 184 138 131 166 143 151 167 17 60 188 92 110 33 9 65 186 74 198 170 144 161 69 134 179 189 191 70 64 79 10 84 65 107 66 149 123 191 184 141 107 30 170 129 159 186 108 132 17 68 46 198 158 41 13 55 101 59 20 72 200 63 128 23 89...
output:
85910356
result:
ok single line: '85910356'
Subtask #8:
score: 7
Accepted
Dependency #7:
100%
Accepted
Test #29:
score: 7
Accepted
time: 12ms
memory: 20512kb
input:
1 1 170 104 123 43 65 8 61 169 138 20 160 34 169 133 25 129 2 115 137 64 168 33 35 77 38 128 166 159 151 78 3 155 34 6 140 16 133 26 117 13 143 144 150 7 131 64 61 162 52 149 16 17 80 136 77 141 83 54 146 85 47 140 24 107 158 91 152 66 43 24 21 86 38 141 85 51 11 162 151 2 66 73 74 9 26 156 68 121 1...
output:
83894725
result:
ok single line: '83894725'
Test #30:
score: 7
Accepted
time: 25ms
memory: 20740kb
input:
1 1 168 46 92 25 154 91 121 21 31 100 152 24 35 115 67 139 111 113 90 88 69 134 83 127 120 74 23 22 108 28 18 58 36 15 125 100 167 3 127 112 34 7 25 3 23 40 13 29 138 124 118 33 143 8 32 17 58 20 120 12 148 158 130 115 122 26 29 90 157 111 73 57 64 79 80 153 159 89 73 50 79 62 105 109 135 96 32 27 1...
output:
314954106
result:
ok single line: '314954106'
Test #31:
score: 7
Accepted
time: 17ms
memory: 22796kb
input:
1 1 173 71 145 155 153 150 80 164 52 158 173 116 96 169 100 59 20 143 151 43 73 66 38 77 161 39 91 166 11 35 136 4 145 65 37 163 67 138 140 170 31 28 124 85 104 27 2 50 129 76 82 69 155 36 33 86 112 58 23 89 40 47 3 64 27 94 110 36 22 47 67 99 19 165 134 55 131 16 118 68 144 45 53 52 35 125 6 120 77...
output:
223769237
result:
ok single line: '223769237'
Test #32:
score: 7
Accepted
time: 60ms
memory: 22592kb
input:
1 1 200 14 29 23 169 138 142 67 145 166 102 126 183 108 69 170 70 85 194 79 132 174 154 30 130 133 21 93 86 68 183 83 168 160 114 4 94 33 11 109 16 98 18 115 27 52 146 88 103 54 7 49 158 121 110 159 55 190 177 193 85 63 8 155 140 43 117 149 93 169 48 125 133 180 95 189 199 78 162 24 144 84 5 135 39 ...
output:
792535599
result:
ok single line: '792535599'
Subtask #9:
score: 10
Accepted
Dependency #8:
100%
Accepted
Test #33:
score: 10
Accepted
time: 22ms
memory: 20672kb
input:
1 2 160 85 103 57 106 55 79 43 92 96 116 100 68 93 88 103 24 70 144 7 12 142 123 95 77 134 15 16 153 98 74 8 150 56 142 47 58 91 54 65 59 77 131 101 47 17 8 10 5 61 97 89 115 46 96 92 36 43 34 159 139 73 28 66 151 44 76 18 13 33 76 127 67 4 33 9 102 126 9 133 141 88 109 32 27 50 117 128 140 126 10 7...
output:
138251585
result:
ok single line: '138251585'
Test #34:
score: 10
Accepted
time: 43ms
memory: 22352kb
input:
1 2 170 18 31 34 76 122 66 130 150 32 115 155 69 153 46 77 92 26 83 15 109 93 116 142 62 133 25 99 114 117 37 64 102 152 122 143 86 157 110 10 16 98 51 96 139 52 45 55 108 78 166 137 142 160 80 45 40 7 94 132 54 9 81 153 141 54 70 4 60 127 91 13 26 120 152 124 161 94 82 106 61 121 30 111 77 160 165 ...
output:
402212722
result:
ok single line: '402212722'
Test #35:
score: 10
Accepted
time: 11ms
memory: 22496kb
input:
1 2 165 164 110 44 89 147 71 66 57 104 142 60 31 125 62 163 158 141 161 15 157 109 54 114 108 143 45 25 10 83 75 88 36 118 122 97 72 79 19 19 72 148 153 79 132 153 3 23 130 7 91 148 17 10 46 78 65 151 85 16 128 137 82 136 162 126 75 72 1 101 117 50 60 43 132 69 63 27 94 110 155 162 33 107 140 124 20...
output:
239138702
result:
ok single line: '239138702'
Test #36:
score: 10
Accepted
time: 36ms
memory: 22876kb
input:
1 2 200 48 108 140 189 123 65 47 102 83 53 173 26 176 45 32 167 99 155 7 91 58 136 85 35 40 147 49 70 75 163 94 114 25 16 128 3 47 172 20 191 4 120 187 38 52 98 30 162 151 85 96 124 169 125 175 74 183 163 178 78 192 154 63 76 175 88 136 5 150 83 54 191 134 145 181 60 151 160 152 141 142 66 100 52 15...
output:
94911555
result:
ok single line: '94911555'
Subtask #10:
score: 10
Accepted
Dependency #9:
100%
Accepted
Test #37:
score: 10
Accepted
time: 7ms
memory: 22648kb
input:
1 31 151 94 56 7 113 142 50 51 81 131 1 25 10 74 106 87 68 43 76 25 91 128 116 12 61 75 34 43 5 36 53 13 41 48 51 40 73 89 69 59 34 62 10 133 107 89 49 139 53 91 97 125 23 35 44 22 135 98 105 4 83 49 26 100 48 2 110 28 52 3 96 46 96 15 6 132 78 109 73 145 81 69 102 54 92 30 56 74 117 11 146 70 26 99...
output:
494673301
result:
ok single line: '494673301'
Test #38:
score: 10
Accepted
time: 11ms
memory: 22692kb
input:
1 36 194 118 43 73 36 56 124 49 9 173 28 81 113 156 117 151 110 5 117 67 187 18 146 70 177 38 65 59 120 115 13 165 78 75 152 146 87 39 48 151 185 85 120 101 62 177 174 133 166 160 105 84 43 128 149 193 49 153 126 99 78 123 98 116 159 106 98 61 20 48 54 182 114 31 92 50 159 45 102 18 50 178 62 147 14...
output:
248295050
result:
ok single line: '248295050'
Test #39:
score: 10
Accepted
time: 4ms
memory: 20468kb
input:
1 36 164 110 58 147 116 133 17 26 1 160 143 11 112 123 113 97 37 138 132 73 80 67 56 138 142 40 33 115 153 52 6 126 81 124 76 122 83 135 114 67 129 109 89 62 76 36 98 57 91 63 64 85 41 155 118 86 13 12 63 77 15 117 54 146 112 118 26 70 72 74 55 128 98 50 28 30 139 29 78 108 66 105 7 21 78 151 104 11...
output:
273498099
result:
ok single line: '273498099'
Test #40:
score: 10
Accepted
time: 7ms
memory: 22864kb
input:
1 40 200 103 35 185 125 34 90 176 65 48 50 42 77 80 105 82 151 144 26 59 173 81 142 41 192 167 198 131 20 126 6 19 179 122 170 116 120 86 178 147 149 89 168 111 6 3 100 24 166 18 34 169 74 17 95 8 73 46 184 154 52 92 83 129 164 190 77 90 37 87 144 200 70 131 16 113 161 181 98 99 139 150 43 200 78 12...
output:
6219604
result:
ok single line: '6219604'
Subtask #11:
score: 0
Time Limit Exceeded
Dependency #10:
100%
Accepted
Test #41:
score: 0
Time Limit Exceeded
input:
1 820 4113 2108 233 4008 3416 4006 2604 1450 3610 1459 246 3094 1565 3052 3604 3985 3162 1804 92 2848 785 259 2585 2085 1942 1910 68 1191 4039 955 4056 1005 4030 2495 3228 4089 2400 439 2097 2861 663 649 3609 3112 3272 3690 1220 2456 1644 2912 2530 408 2209 2105 2253 851 51 419 3407 2193 2784 280 26...