QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#405486 | #7613. Inverse Problem | ucup-team3215 | AC ✓ | 33089ms | 816240kb | C++20 | 3.0kb | 2024-05-06 00:46:40 | 2024-05-06 00:46:40 |
Judging History
answer
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
constexpr int mod = 1e9 + 7, cut = 6;
auto& mul(auto&& a, auto b) { return a = a * (uint64_t) b % mod; }
int inv(int a) { for (int r = 1, b = mod - 2; ; b /= 2, mul(a, a)) if (!b) return r; else if (b % 2) mul(r, a); }
using namespace std;
template <typename K, typename V, int mlf = 4>
struct HT {
int capacity;
vector<pair<K, int>> knx;
vector<V> values;
vector<int> head;
HT(): capacity{4 * mlf}, head(capacity, -1) {
}
void emplace(K k, V v) {
// if (~find(k)) return;
knx.push_back({k, head[k & capacity - 1]});
values.push_back(v);
head[k & capacity - 1] = knx.size() - 1;
maybe_rehash();
}
int find(K k) {
for (int i = head[k & capacity - 1]; ~i; i = knx[i].second) if (knx[i].first == k) return i;
return -1;
}
void clear() {
knx.clear();
values.clear();
head.assign(capacity, -1);
}
void maybe_rehash() {
if (knx.size() * mlf <= capacity) return;
head.assign(capacity *= 2, -1);
for (int i = 0; i < knx.size(); ++i) {
knx[i].second = head[knx[i].first & capacity - 1];
head[knx[i].first & capacity - 1] = i;
}
}
};
vector<HT<int, vector<int>>> high(1);
vector<int> inv_(1);
void gen_high(int n0, int n, int c, int p, auto&& cur) {
high[n0 - n].emplace(p, cur);
for (; c > cut; --c) if (c <= n) {
int np = p;
for (int i = 0; i < c; ++i) mul(np, inv_[n0 - i]);
cur.push_back(c);
gen_high(n0, n - c, c, np, cur);
cur.pop_back();
}
}
vector<int> qs;
vector<vector<int>> ans;
void solve(int n0, int n, int c, int p, auto&& cur) {
for (int i = 0; i < qs.size(); ++i) if (ans[i].empty() && ~high[n].find(mul(+p, qs[i]))) {
ans[i] = cur;
auto& t = high[n].values[high[n].find(mul(+p, qs[i]))];
ans[i].insert(ans[i].end(), t.begin(), t.end());
}
for (; c > 0; --c) if (c <= n) {
int np = p;
for (int i = 0; i < c; ++i) mul(np, n0 - i);
cur.push_back(c);
solve(n0, n - c, c, np, cur);
cur.pop_back();
}
}
int main() {
int tc; cin >> tc;
qs.resize(tc);
ans.resize(tc);
for (int i = 0; i < tc; ++i) {
cin >> qs[i];
if (qs[i] == 1) ans[i] = {-1};
else if (qs[i] == 2) ans[i] = {-1};
qs[i] = inv(qs[i]);
}
for (int n = 1, done = 0; !done++; ++n) {
inv_.push_back(inv(n));
high.push_back({});
for (auto& x: high) x.clear();
gen_high(n, n, n, 1, vector<int>{});
solve(n, n, cut, mul(n + 1, n + 2), vector<int>{});
for (int i = 0; i < tc; ++i) done &= !ans[i].empty();
}
for (int i = 0; i < tc; ++i) {
if (qs[i] == 1) cout << "1\n";
else {
if (ans[i][0] == -1) ans[i] = {};
cout << accumulate(ans[i].begin(), ans[i].end(), 0) + 2 << '\n' << "1 2\n";
for (int j = 0, k = 2; j < ans[i].size(); ++j)
while (ans[i][j]--) cout << j + 1 << ' ' << ++k << '\n';
}
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3556kb
input:
4 2 360 1 509949433
output:
2 1 2 5 1 2 1 3 1 4 2 5 1 10 1 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10
result:
ok OK (4 test cases)
Test #2:
score: 0
Accepted
time: 29378ms
memory: 814712kb
input:
9 185396120 468170792 837583517 696626231 338497514 762842660 800028852 928391161 733524004
output:
14 1 2 1 3 1 4 2 5 2 6 3 7 4 8 5 9 6 10 7 11 8 12 9 13 10 14 122 1 2 1 3 1 4 1 5 1 6 1 7 1 8 2 9 2 10 2 11 3 12 3 13 3 14 4 15 4 16 4 17 5 18 5 19 5 20 6 21 6 22 6 23 7 24 7 25 8 26 8 27 9 28 9 29 10 30 11 31 12 32 13 33 14 34 15 35 16 36 17 37 18 38 19 39 20 40 21 41 22 42 23 43 23 44 23 45 23 46 2...
result:
ok OK (9 test cases)
Test #3:
score: 0
Accepted
time: 33089ms
memory: 816240kb
input:
10 338497514 733524004 447182954 415993605 453460670 50499055 648088551 986982752 907925397 315315230
output:
124 1 2 1 3 1 4 1 5 1 6 1 7 1 8 2 9 2 10 2 11 2 12 2 13 3 14 3 15 3 16 4 17 4 18 5 19 6 20 7 21 8 22 9 23 10 24 11 25 12 26 13 27 14 28 15 29 15 30 15 31 15 32 15 33 15 34 15 35 15 36 15 37 15 38 15 39 15 40 15 41 15 42 15 43 15 44 15 45 15 46 15 47 15 48 15 49 15 50 15 51 15 52 15 53 15 54 15 55 15...
result:
ok OK (10 test cases)
Test #4:
score: 0
Accepted
time: 4716ms
memory: 128052kb
input:
10 1 2 3 4 5 6 7 8 9 10
output:
1 2 1 2 102 1 2 1 3 1 4 1 5 1 6 1 7 1 8 2 9 2 10 3 11 3 12 4 13 4 14 5 15 5 16 6 17 6 18 7 19 8 20 9 21 10 22 10 23 10 24 10 25 10 26 10 27 10 28 10 29 10 30 10 31 10 32 10 33 10 34 10 35 10 36 10 37 10 38 10 39 10 40 10 41 10 42 10 43 10 44 11 45 11 46 11 47 11 48 11 49 11 50 11 51 11 52 11 53 11 5...
result:
ok OK (10 test cases)
Test #5:
score: 0
Accepted
time: 1246ms
memory: 36344kb
input:
10 269199917 392009324 753889928 751355133 472639410 132096559 331333826 40414701 72847302 475706026
output:
55 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 84 1 2 1 3 1 4 1 5 1 6 1 7 1 8 2 9 ...
result:
ok OK (10 test cases)
Extra Test:
score: 0
Extra Test Passed