QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #108653 | #5573. Holiday Regifting | LG_Monkey | TL | 263ms | 3808kb | C++14 | 1.2kb | 2023-05-25 21:57:22 | 2023-05-25 21:57:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define deb(var) cerr << #var << '=' << (var) << "; "
#define ll long long
int n, m, c[10010];
const int mod = 998244353;
int head[10010];
struct Ed {
int v, nxt;
} e[50010]; int tot;
ll ind[10010], ord[10010], f[10010];
void mmod(ll &x, ll m) {
x = x - x / m * m;
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> c[i];
while (m--) {
int u, v;
cin >> u >> v;
e[++tot].v = v; e[tot].nxt = head[u]; head[u] = tot;
}
ll ans = c[1];
f[1] = ans;
for (int j = 1; j <= n; j++) {
int u = j;
for (int k = head[u]; k; k = e[k].nxt) {
int v = e[k].v;
f[v] += f[u] / c[u];
}
f[u] %= c[u];
}
for (int i = 2; i <= n; i++) {
int u = i;
int o = c[u] / __gcd(f[u], (ll)c[u]);
for (int u = 1; u <= n; u++) f[u] *= o;
for (int j = 1; j <= n; j++) {
int u = j;
for (int k = head[u]; k; k = e[k].nxt) {
int v = e[k].v;
f[v] += f[u] / c[u];
}
mmod(f[u], c[u]);
}
ans = ans * o % mod;
}
cout << ans;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3340kb
input:
5 10 4 3 2 2 2 1 3 3 4 1 4 1 5 2 5 2 4 1 2 2 3 3 5 4 5
output:
24
result:
ok 1 number(s): "24"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3432kb
input:
3 0 95 13 77
output:
95
result:
ok 1 number(s): "95"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3396kb
input:
12 14 6 7 17 16 20 14 17 16 6 11 6 14 4 11 3 5 2 5 9 11 7 12 1 3 5 9 3 7 3 8 4 9 1 9 4 7 2 11 1 12
output:
8739360
result:
ok 1 number(s): "8739360"
Test #4:
score: 0
Accepted
time: 2ms
memory: 3348kb
input:
1 0 2
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3396kb
input:
50 97 2 2 2 2 2 11 13 7 2 2 2 2 2 2 5 2 5 2 3 2 2 2 2 2 2 2 2 13 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 17 26 17 24 17 38 15 28 23 28 45 50 16 28 7 37 7 31 5 28 2 28 13 28 6 40 3 40 3 7 44 46 11 40 12 28 15 29 15 17 28 49 5 48 6 19 28 41 7 17 27 28 33 38 26 28 2 39 32 40 8 17 17 28 28 42 6 46 2...
output:
68640
result:
ok 1 number(s): "68640"
Test #6:
score: 0
Accepted
time: 126ms
memory: 3592kb
input:
500 30000 109 118 125 106 124 114 125 118 110 113 121 132 102 113 117 118 131 104 113 116 113 114 98 134 123 135 124 124 105 105 98 108 118 109 105 117 109 104 109 116 100 112 106 109 113 103 113 108 111 97 125 96 102 106 130 107 111 94 124 104 109 113 101 100 95 105 101 100 106 100 106 86 105 83 11...
output:
442991751
result:
ok 1 number(s): "442991751"
Test #7:
score: 0
Accepted
time: 131ms
memory: 3800kb
input:
500 30000 112 97 177 122 108 104 111 119 95 114 116 101 202 107 108 117 95 151 113 110 96 103 107 119 119 97 110 92 114 129 109 103 113 118 107 118 104 93 102 257 125 113 101 117 122 100 107 97 105 95 121 100 97 106 105 113 95 75 92 94 120 106 96 82 126 83 89 88 101 93 100 95 98 100 112 116 95 91 91...
output:
834101312
result:
ok 1 number(s): "834101312"
Test #8:
score: 0
Accepted
time: 126ms
memory: 3784kb
input:
500 30000 170 111 96 103 118 120 92 97 93 109 93 97 127 170 101 182 97 98 99 132 99 101 95 107 105 198 85 102 91 127 111 102 85 92 101 97 91 116 161 137 101 97 101 93 84 80 99 298 89 100 98 87 109 100 104 94 117 109 89 91 105 106 78 91 106 92 124 94 85 118 92 85 91 101 85 90 88 180 90 86 86 84 93 19...
output:
571291789
result:
ok 1 number(s): "571291789"
Test #9:
score: 0
Accepted
time: 131ms
memory: 3788kb
input:
500 30000 115 123 123 130 131 103 116 122 103 112 156 138 139 140 117 116 95 129 99 112 102 134 142 123 119 94 120 95 117 106 129 113 91 102 102 118 112 118 135 114 94 110 88 98 105 116 106 116 113 101 124 112 111 102 93 106 96 118 106 112 106 104 109 97 102 116 88 109 103 103 110 93 108 100 107 86 ...
output:
688436837
result:
ok 1 number(s): "688436837"
Test #10:
score: 0
Accepted
time: 136ms
memory: 3700kb
input:
500 30000 110 87 92 129 127 143 128 129 204 93 106 97 94 136 267 108 95 104 147 174 115 106 88 99 106 85 101 105 95 90 129 109 118 111 90 91 206 146 104 170 225 120 93 107 89 100 77 83 174 126 92 93 104 91 83 85 107 87 94 95 100 105 115 122 104 102 85 139 92 235 83 93 85 114 89 82 93 81 90 82 95 104...
output:
710426457
result:
ok 1 number(s): "710426457"
Test #11:
score: 0
Accepted
time: 131ms
memory: 3588kb
input:
500 30000 99 120 148 141 107 99 119 116 94 216 94 88 98 100 118 176 107 104 97 93 105 88 98 103 102 88 85 368 293 103 87 93 98 97 105 118 95 110 92 96 92 115 143 123 118 107 96 117 92 108 97 83 86 91 127 101 83 81 92 82 81 354 87 91 108 113 256 91 120 117 93 98 77 80 90 85 94 83 91 89 79 100 183 91 ...
output:
696400494
result:
ok 1 number(s): "696400494"
Test #12:
score: 0
Accepted
time: 263ms
memory: 3628kb
input:
1000 30000 65 47 56 43 65 65 55 53 62 52 62 62 58 64 47 60 53 56 55 65 55 50 70 48 54 57 57 59 54 57 60 45 55 56 45 67 56 48 67 55 62 71 68 54 50 60 48 57 64 57 58 56 52 54 48 64 44 58 49 49 53 45 55 60 60 53 56 51 72 62 62 56 66 53 55 54 43 48 47 75 49 47 54 57 47 50 65 60 48 57 47 52 60 50 57 47 3...
output:
152837418
result:
ok 1 number(s): "152837418"
Test #13:
score: 0
Accepted
time: 257ms
memory: 3808kb
input:
1000 30000 49 43 53 65 56 52 64 52 64 75 55 59 52 67 59 46 49 60 59 58 66 52 47 57 56 49 79 61 57 59 58 68 49 63 50 43 46 48 49 71 59 53 50 46 53 40 58 47 54 55 59 60 70 61 53 59 52 53 54 43 60 58 51 57 52 55 44 63 50 56 47 46 57 53 67 57 50 61 45 58 50 52 60 47 47 60 57 73 57 51 54 43 52 46 58 43 5...
output:
258066129
result:
ok 1 number(s): "258066129"
Test #14:
score: -100
Time Limit Exceeded
input:
10000 30000 5 11 4 4 6 5 7 5 7 3 4 3 8 3 6 7 5 4 4 3 4 4 7 8 4 6 4 5 4 3 4 3 4 3 6 9 5 5 3 5 7 6 6 3 4 3 7 6 4 5 7 5 7 7 4 4 7 8 5 5 7 7 4 2 6 4 4 4 3 5 5 3 6 6 7 8 5 6 4 3 4 7 4 3 6 5 4 4 7 6 4 8 5 6 5 3 3 6 5 5 5 5 6 6 6 8 8 6 7 2 6 5 3 5 6 3 6 5 4 3 6 5 3 4 5 6 2 7 5 5 11 7 7 5 4 3 4 4 5 5 5 6 4 ...