QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #180156 | #7128. Huge products | ucup-team004# | WA | 34ms | 6260kb | C++20 | 5.4kb | 2023-09-15 16:13:30 | 2023-09-15 16:13:31 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
constexpr int P = 1000000007;
const std::vector<std::vector<std::pair<int, int>>> d {
{{5, -1}, {6, 2}, {8, -1}, {9, -1}, {10, 1}},
{{5, -1}, {6, -4}, {8, 1}, {9, 2}, {10, 1}},
{{5, -2}, {6, -2}, {9, 1}, {10, 2}},
{{5, -3}, {8, -1}, {10, 3}},
{{4, -1}, {5, 1}, {8, 1}, {10, -1}},
{{4, -1}, {6, 2}, {9, -1}},
{{4, -1}, {6, -4}, {8, 2}, {9, 2}},
{{4, -1}, {5, -1}, {6, -2}, {8, 1}, {9, 1}, {10, 1}},
{{4, -1}, {5, -2}, {10, 2}},
{{4, -2}, {6, -2}, {8, 2}, {9, 1}},
{{4, -2}, {5, -1}, {8, 1}, {10, 1}},
{{4, -3}, {8, 2}},
{{3, -1}, {5, 1}, {6, 1}, {10, -1}},
{{3, -1}, {4, 1}, {6, 1}, {8, -1}},
{{3, -1}, {6, 3}, {8, -1}, {9, -1}},
{{3, -1}, {6, -3}, {8, 1}, {9, 2}},
{{3, -1}, {4, 1}, {5, 1}, {6, -1}, {9, 1}, {10, -1}},
{{3, -1}, {5, 2}, {6, -1}, {8, 1}, {9, 1}, {10, -2}},
{{3, -1}, {4, 2}, {6, -1}, {8, -1}, {9, 1}},
{{3, -1}, {5, -1}, {6, -1}, {9, 1}, {10, 1}},
{{3, -1}, {5, -2}, {6, 1}, {8, -1}, {10, 2}},
{{3, -1}, {4, -1}, {6, -1}, {8, 1}, {9, 1}},
{{3, -1}, {4, -1}, {5, -1}, {6, 1}, {10, 1}},
{{3, -1}, {4, -2}, {6, 1}, {8, 1}},
{{3, -2}, {9, 1}},
{{3, -2}, {5, -1}, {6, 2}, {8, -1}, {10, 1}},
{{3, -2}, {4, -1}, {6, 2}},
{{3, -3}, {6, 3}, {8, -1}},
{{2, -1}, {4, 1}, {5, 1}, {10, -1}},
{{2, -1}, {5, 2}, {8, 1}, {10, -2}},
{{2, -1}, {3, 1}, {6, 1}, {9, -1}},
{{2, -1}, {5, 1}, {6, 2}, {9, -1}, {10, -1}},
{{2, -1}, {4, 2}, {8, -1}},
{{2, -1}, {4, 1}, {6, 2}, {8, -1}, {9, -1}},
{{2, -1}, {6, 4}, {8, -1}, {9, -2}},
{{2, -1}, {3, 1}, {4, 1}, {6, -1}},
{{2, -1}, {6, -2}, {8, 1}, {9, 1}},
{{2, -1}, {5, -1}, {10, 1}},
{{2, -1}, {4, -1}, {8, 1}},
{{2, -1}, {3, -1}, {6, 1}},
{{2, -1}, {3, -1}, {4, 1}, {6, -1}, {9, 1}},
{{2, -1}, {3, -1}, {5, 1}, {6, -1}, {8, 1}, {9, 1}, {10, -1}},
{{2, -2}, {4, 1}},
{{2, -2}, {5, 1}, {8, 1}, {10, -1}},
{{2, -2}, {6, 2}, {9, -1}},
{{2, -2}, {3, 1}, {6, -1}, {8, 1}},
{{2, -2}, {3, -1}, {6, -1}, {8, 1}, {9, 1}},
{{2, -3}, {8, 1}},
{{1, -1}}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
i64 a[11];
for (int i = 1; i <= 10; i++) {
std::cin >> a[i];
}
// a[1] = 0;
// if (a[2]) {
// a[2] += a[4] * 2;
// a[4] = 0;
// }
// if (a[3]) {
// a[3] += a[9] * 2;
// a[9] = 0;
// }
// if (a[2] >= 2) {
// a[2] += a[8] * 3;
// a[8] = 0;
// }
std::map<std::vector<int>, int> f;
f[std::vector<int>(21)] = 1;
for (auto u : d) {
auto g = f;
for (auto [x, y] : g) {
if (y == 0) {
f.erase(x);
}
}
for (auto [x, y] : g) {
if (y == 0) {
continue;
}
auto nx = x;
for (auto [a, b] : u) {
nx[a] = std::max(nx[a], b);
nx[a + 10] = std::min(nx[a + 10], b);
}
f[nx] = (f[nx] + 1LL * (P - 1) * y) % P;
}
}
// if (a[2] < 100) {
// using i128 = __int128;
// // std::set<i128> s;
// std::map<i128, std::vector<int>> s;
// std::vector<int> cnt(11);
// std::vector<std::vector<int>> d;
// auto dfs = [&](auto self, int x, i128 v) {
// if (x == 11) {
// if (!s.count(v)) {
// s[v] = cnt;
// } else {
// std::vector<int> x(11);
// for (int i = 1; i <= 10; i++) {
// x[i] = s[v][i] - cnt[i];
// }
// bool add = true;
// for (auto u : d) {
// bool ok = false;
// for (int i = 1; i <= 10; i++) {
// if (x[i] > 0 && u[i] < 0 || x[i] < 0 && u[i] > 0 || std::abs(x[i]) < std::abs(u[i])) {
// ok = true;
// }
// }
// if (!ok) {
// add = false;
// }
// }
// if (add) {
// d.push_back(x);
// std::cout << "{";
// for (int i = 1; i <= 10; i++) {
// if (x[i]) {
// std::cout << "{" << i << ", " << x[i] << "}, ";
// }
// }
// std::cout << "},\n";
// }
// }
// return;
// }
// for (int i = 0; i <= a[x]; i++) {
// if (i) {
// v *= x;
// }
// cnt[x] = i;
// self(self, x + 1, v);
// }
// };
// dfs(dfs, 1, 1);
// std::cout << s.size() << "\n";
// }
int ans = 0;
for (auto [x, y] : f) {
int res = 1;
for (int i = 1; i <= 10; i++) {
res = 1LL * res * std::max(0LL, a[i] + 1 - x[i] + x[i + 10]) % P;
}
ans = (ans + 1LL * res * (y + P)) % P;
}
std::cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 34ms
memory: 5952kb
input:
0 1 0 1 0 0 0 1 0 0
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 29ms
memory: 5956kb
input:
0 1000000000 100000000 0 0 0 0 0 0 0
output:
400000001
result:
ok 1 number(s): "400000001"
Test #3:
score: 0
Accepted
time: 33ms
memory: 6024kb
input:
5 1 1 5 0 0 3 4 4 0
output:
960
result:
ok 1 number(s): "960"
Test #4:
score: 0
Accepted
time: 33ms
memory: 5960kb
input:
0 3 4 0 1 0 2 2 0 2
output:
630
result:
ok 1 number(s): "630"
Test #5:
score: 0
Accepted
time: 30ms
memory: 6212kb
input:
2 1 0 0 0 1 3 0 0 0
output:
16
result:
ok 1 number(s): "16"
Test #6:
score: 0
Accepted
time: 34ms
memory: 6180kb
input:
2 1 0 0 0 0 0 0 0 3
output:
8
result:
ok 1 number(s): "8"
Test #7:
score: 0
Accepted
time: 29ms
memory: 5996kb
input:
0 2 2 0 2 0 5 5 3 0
output:
2916
result:
ok 1 number(s): "2916"
Test #8:
score: 0
Accepted
time: 33ms
memory: 5944kb
input:
1 0 1 2 1 4 3 0 0 1
output:
400
result:
ok 1 number(s): "400"
Test #9:
score: 0
Accepted
time: 33ms
memory: 6180kb
input:
3 2 2 1 0 4 1 3 4 0
output:
500
result:
ok 1 number(s): "500"
Test #10:
score: 0
Accepted
time: 29ms
memory: 6212kb
input:
1 0 2 2 0 3 3 0 0 0
output:
128
result:
ok 1 number(s): "128"
Test #11:
score: 0
Accepted
time: 30ms
memory: 5900kb
input:
5 3 0 2 0 1 1 0 3 0
output:
128
result:
ok 1 number(s): "128"
Test #12:
score: 0
Accepted
time: 33ms
memory: 6024kb
input:
0 2 1 2 0 2 1 0 0 1
output:
120
result:
ok 1 number(s): "120"
Test #13:
score: 0
Accepted
time: 29ms
memory: 5904kb
input:
4 0 0 2 0 1 3 0 0 0
output:
24
result:
ok 1 number(s): "24"
Test #14:
score: 0
Accepted
time: 33ms
memory: 5952kb
input:
2 2 1 2 0 2 3 0 3 0
output:
336
result:
ok 1 number(s): "336"
Test #15:
score: 0
Accepted
time: 33ms
memory: 6016kb
input:
4 0 1 0 4 0 2 1 0 0
output:
60
result:
ok 1 number(s): "60"
Test #16:
score: 0
Accepted
time: 34ms
memory: 6016kb
input:
1 0 1 2 1 0 5 0 4 0
output:
360
result:
ok 1 number(s): "360"
Test #17:
score: 0
Accepted
time: 26ms
memory: 6256kb
input:
3 1 0 1 0 0 5 0 5 2
output:
432
result:
ok 1 number(s): "432"
Test #18:
score: 0
Accepted
time: 33ms
memory: 5900kb
input:
1 1 0 4 0 3 0 0 5 0
output:
160
result:
ok 1 number(s): "160"
Test #19:
score: 0
Accepted
time: 33ms
memory: 5948kb
input:
5 1 0 0 3 5 2 1 1 0
output:
528
result:
ok 1 number(s): "528"
Test #20:
score: 0
Accepted
time: 33ms
memory: 6020kb
input:
2 0 0 0 0 0 1 0 2 0
output:
6
result:
ok 1 number(s): "6"
Test #21:
score: 0
Accepted
time: 25ms
memory: 5944kb
input:
4 2 0 1 0 0 4 3 0 0
output:
70
result:
ok 1 number(s): "70"
Test #22:
score: 0
Accepted
time: 33ms
memory: 5988kb
input:
0 0 0 2 0 4 2 0 0 0
output:
45
result:
ok 1 number(s): "45"
Test #23:
score: 0
Accepted
time: 33ms
memory: 5992kb
input:
4 2 1 5 2 0 1 0 2 1
output:
648
result:
ok 1 number(s): "648"
Test #24:
score: 0
Accepted
time: 33ms
memory: 6020kb
input:
3 0 4 0 3 3 1 4 0 5
output:
2200
result:
ok 1 number(s): "2200"
Test #25:
score: 0
Accepted
time: 33ms
memory: 6256kb
input:
1 2 0 1 0 0 2 0 1 0
output:
30
result:
ok 1 number(s): "30"
Test #26:
score: 0
Accepted
time: 29ms
memory: 6236kb
input:
3 0 1 1 1 0 2 0 5 0
output:
144
result:
ok 1 number(s): "144"
Test #27:
score: 0
Accepted
time: 30ms
memory: 6016kb
input:
5 0 2 1 4 4 0 0 0 3
output:
312
result:
ok 1 number(s): "312"
Test #28:
score: 0
Accepted
time: 33ms
memory: 6056kb
input:
0 1 5 2 0 2 3 0 3 0
output:
424
result:
ok 1 number(s): "424"
Test #29:
score: 0
Accepted
time: 29ms
memory: 6020kb
input:
2 1 1 3 0 0 4 0 0 0
output:
80
result:
ok 1 number(s): "80"
Test #30:
score: 0
Accepted
time: 29ms
memory: 6020kb
input:
4 1 3 0 0 5 3 0 5 0
output:
412
result:
ok 1 number(s): "412"
Test #31:
score: 0
Accepted
time: 33ms
memory: 6184kb
input:
0 3 0 0 0 2 2 0 0 4
output:
180
result:
ok 1 number(s): "180"
Test #32:
score: 0
Accepted
time: 34ms
memory: 5948kb
input:
4 1 1 4 0 0 4 0 0 5
output:
600
result:
ok 1 number(s): "600"
Test #33:
score: 0
Accepted
time: 33ms
memory: 6044kb
input:
5 2 1 2 5 0 5 1 0 4
output:
1440
result:
ok 1 number(s): "1440"
Test #34:
score: 0
Accepted
time: 33ms
memory: 6020kb
input:
3 1 0 1 3 1 2 4 1 2
output:
1224
result:
ok 1 number(s): "1224"
Test #35:
score: 0
Accepted
time: 26ms
memory: 6260kb
input:
1 0 1 2 0 0 1 3 3 0
output:
192
result:
ok 1 number(s): "192"
Test #36:
score: 0
Accepted
time: 33ms
memory: 5884kb
input:
3 2 0 2 0 2 4 0 0 0
output:
105
result:
ok 1 number(s): "105"
Test #37:
score: 0
Accepted
time: 34ms
memory: 5960kb
input:
0 0 0 1 0 1 1 0 3 0
output:
32
result:
ok 1 number(s): "32"
Test #38:
score: 0
Accepted
time: 29ms
memory: 6256kb
input:
2 2 4 2 0 0 4 0 0 4
output:
875
result:
ok 1 number(s): "875"
Test #39:
score: 0
Accepted
time: 33ms
memory: 5952kb
input:
0 1 3 2 2 0 3 0 0 5
output:
928
result:
ok 1 number(s): "928"
Test #40:
score: 0
Accepted
time: 29ms
memory: 5960kb
input:
4 1 0 2 1 4 5 0 1 2
output:
1236
result:
ok 1 number(s): "1236"
Test #41:
score: 0
Accepted
time: 33ms
memory: 5956kb
input:
1 1 1 2 0 0 5 3 0 0
output:
180
result:
ok 1 number(s): "180"
Test #42:
score: 0
Accepted
time: 30ms
memory: 6208kb
input:
5 3 1 1 0 0 0 0 2 0
output:
36
result:
ok 1 number(s): "36"
Test #43:
score: 0
Accepted
time: 33ms
memory: 6056kb
input:
5 1 0 1 0 1 4 1 3 0
output:
280
result:
ok 1 number(s): "280"
Test #44:
score: 0
Accepted
time: 29ms
memory: 6012kb
input:
3 2 0 2 2 3 1 0 0 0
output:
168
result:
ok 1 number(s): "168"
Test #45:
score: 0
Accepted
time: 33ms
memory: 5900kb
input:
5 1 4 4 0 1 2 1 1 0
output:
330
result:
ok 1 number(s): "330"
Test #46:
score: 0
Accepted
time: 33ms
memory: 5988kb
input:
0 0 1 0 3 0 0 0 0 0
output:
8
result:
ok 1 number(s): "8"
Test #47:
score: 0
Accepted
time: 30ms
memory: 5956kb
input:
2 2 0 0 0 0 3 0 0 5
output:
72
result:
ok 1 number(s): "72"
Test #48:
score: 0
Accepted
time: 33ms
memory: 6184kb
input:
4 0 5 1 0 0 4 0 0 0
output:
60
result:
ok 1 number(s): "60"
Test #49:
score: 0
Accepted
time: 29ms
memory: 5892kb
input:
0 2 1 2 3 0 1 3 0 0
output:
256
result:
ok 1 number(s): "256"
Test #50:
score: 0
Accepted
time: 25ms
memory: 5952kb
input:
1 0 1 2 0 0 2 0 0 2
output:
54
result:
ok 1 number(s): "54"
Test #51:
score: 0
Accepted
time: 33ms
memory: 5908kb
input:
3 3 1 0 0 5 5 4 5 0
output:
1962
result:
ok 1 number(s): "1962"
Test #52:
score: 0
Accepted
time: 34ms
memory: 5952kb
input:
5 0 0 1 0 0 5 0 5 5
output:
432
result:
ok 1 number(s): "432"
Test #53:
score: 0
Accepted
time: 33ms
memory: 5896kb
input:
98085918 0 1 0 0 355431774 584158301 250629166 0 0
output:
269418441
result:
ok 1 number(s): "269418441"
Test #54:
score: 0
Accepted
time: 33ms
memory: 6260kb
input:
940350702 0 559496198 264431242 219676070 193178866 415296654 0 0 0
output:
777329375
result:
ok 1 number(s): "777329375"
Test #55:
score: 0
Accepted
time: 33ms
memory: 5892kb
input:
151211705 0 508398953 673816570 996622761 0 394401161 898597245 601916151 532212287
output:
129253427
result:
ok 1 number(s): "129253427"
Test #56:
score: -100
Wrong Answer
time: 26ms
memory: 5952kb
input:
993476489 0 1 415966121 0 110005939 770310760 156975250 215145588 454036580
output:
875792949
result:
wrong answer 1st numbers differ - expected: '450367235', found: '875792949'