QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#406190 | #7613. Inverse Problem | ucup-team3215 | AC ✓ | 3260ms | 5024kb | C++20 | 5.3kb | 2024-05-06 22:07:41 | 2024-05-06 22:07:42 |
Judging History
answer
#include <array>
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
constexpr int mod = 1e9 + 7;
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;
struct HS {
static constexpr int mlf = 2;
int cap;
vector<array<int, 2>> knx;
vector<int> head;
HS(): cap{4 * mlf - 1}, head(cap + 1, -1) {
}
void emplace(int k) {
knx.push_back({k, head[k & cap]});
head[k & cap] = knx.size() - 1;
maybe_rehash();
}
int find(int k) {
#pragma GCC unroll 2
for (int i = head[k & cap]; ~i; i = knx[i][1]) if (knx[i][0] == k) return i;
return -1;
}
void clear() {
knx.clear();
head.assign(cap + 1, -1);
}
void maybe_rehash() {
if (knx.size() * mlf <= cap) return;
head.assign((cap += cap + 1) + 1, -1);
for (int i = 0; i < knx.size(); ++i) {
knx[i][1] = head[knx[i][0] & cap];
head[knx[i][0] & cap] = i;
}
}
};
vector<HS> high;
vector<int> inva, fa;
vector<char> done;
vector<vector<array<int, 2>>> found;
vector<int> qs;
vector<vector<int>> ans;
vector<int> idxs;
int to_restore;
void gen_high(const vector<int>& prof, int n0, int n, int c, int p) {
high[n0 - n].emplace(p);
for (int cc = prof[n]; ++cc <= min(n, c); ) gen_high(prof, n0, n - cc, cc, mul(+p, inva[cc]));
}
void restore_high(const vector<int>& prof, int n0, int n, int c) {
static int cur[999], sz;
while (found[n0 - n].size() && found[n0 - n].back()[0] == idxs[n0 - n]) {
auto [x, i] = found[n0 - n].back();
ans[i].insert(ans[i].end(), cur, cur + sz);
found[n0 - n].pop_back();
if (!--to_restore) return;
}
++idxs[n0 - n];
for (int cc = prof[n]; ++cc <= min(n, c); ) cur[sz++] = cc, restore_high(prof, n0, n - cc, cc), --sz;
}
void solve(const vector<int>& prof, int n0, int n, int c, int p) {
static int cur[999], sz;
for (int i = 0; i < qs.size(); ++i) if (!done[i] && ~high[n0 - n].find(mul(+p, qs[i]))) {
done[i] = 1;
ans[i].insert(ans[i].end(), cur, cur + sz);
found[n0 - n].push_back({high[n0 - n].find(mul(+p, qs[i])), i});
++to_restore;
}
for (; n + c <= n0 && c <= prof[n + c]; ++c) cur[sz++] = c, solve(prof, n0, n + c, c, mul(+p, fa[c])), --sz;
}
uint64_t eval_high(vector<int> profile) {
int N = profile.size();
vector<uint64_t> cnt(N * N);
cnt[N * N - 1] = 1;
uint64_t ans = 0;
for (int n = N; --n; )
for (int c = N; --c; ) if (cnt[n * N + c]) {
for (int cc = min(n, c); cc > profile[n]; cc--) {
cnt[(n - cc) * N + cc] += cnt[n * N + c];
}
ans += cnt[n * N + c];
}
return ans;
}
uint64_t eval_low(vector<int> profile) {
int N = profile.size();
vector<uint64_t> cnt(N * N);
cnt[0] = 1;
uint64_t ans = 0;
for (int n = 0; n < N; ++n)
for (int c = 0; c <= n; ++c) if (cnt[n * N + c]) {
for (int cc = max(c, 1); n + cc < N && cc <= profile[n + cc]; ++cc) {
cnt[(n + cc) * N + cc] += cnt[n * N + c];
}
ans += cnt[n * N + c];
}
return ans;
}
uint64_t eval(vector<int> profile) {
return eval_high(profile) * 32 + eval_low(profile);
}
vector<int> makeprof(int n, vector<int> from) {
vector<int> prof(n + 1, 0);
int j = n;
for (int i = 0; i < from.size() - 1; ++i) {
while (j >= from[i]) prof[j--] = i;
}
while (j >= 0) prof[j--] = n;
return prof;
}
vector<int> getopt(int n) {
static vector<vector<int>> precalc = [] {
int n = 124;
vector<vector<int>> res(n);
vector<int> tmpl(10, n);
while (n-- > 1) {
int64_t bst = eval(makeprof(n, tmpl));
for (int ch = 1; ch--; ) {
for (int i = 1; i < tmpl.size() - 1; ++i)
for (auto d: {-1, 1}) if (tmpl[i] + d >= 0 && tmpl[i] + d <= n + 1) {
tmpl[i] += d;
int64_t cur = eval(makeprof(n, tmpl));
if (cur > bst) tmpl[i] -= d;
else if (cur < bst) ch = 1, bst = cur;
sort(tmpl.rbegin() + 1, tmpl.rend());
}
}
res[n] = tmpl;
}
return res;
}();
return makeprof(n, precalc[n]);
}
int main() {
int tc; cin >> tc;
qs.resize(tc);
ans.resize(tc);
for (int i = 0; i < tc; ++i) {
cin >> qs[i];
done.push_back(qs[i] <= 2);
qs[i] = inv(qs[i]);
}
for (int n = 1; !all_of(done.begin(), done.end(), identity{}); ++n) {
inva.assign(n + 1, 1);
fa.assign(n + 1, 1);
for (int i = 1; i <= n; ++i) inva[i] = mul(inv(n - i + 1), inva[i - 1]),
fa[i] = mul(n - i + 1, fa[i - 1]);
high.resize(n + 1);
found.resize(n + 1);
idxs.assign(n + 1, 0);
for (auto& x: high) x.clear();
gen_high(getopt(n), n, n, n, 1);
solve(getopt(n), n, 0, 1, mul(n + 1, n + 2));
if (to_restore) {
for (auto& x: found) sort(x.rbegin(), x.rend());
restore_high(getopt(n), n, n, n);
}
}
for (int i = 0; i < tc; ++i) {
if (qs[i] == 1) cout << "1\n";
else {
cout << accumulate(ans[i].begin(), ans[i].end(), 0) + 2 << "\n1 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: 129ms
memory: 3680kb
input:
4 2 360 1 509949433
output:
2 1 2 5 1 2 1 3 2 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: 1897ms
memory: 4984kb
input:
9 185396120 468170792 837583517 696626231 338497514 762842660 800028852 928391161 733524004
output:
14 1 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 9 12 10 13 10 14 122 1 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 14 17 15 18 15 19 16 20 16 21 17 22 17 23 17 24 18 25 18 26 18 27 19 28 19 29 19 30 20 31 20 32 20 33 21 34 21 35 21 36 22 37 22 38 22 39 22 40 22 41 22 42 23 43 ...
result:
ok OK (9 test cases)
Test #3:
score: 0
Accepted
time: 3260ms
memory: 5024kb
input:
10 338497514 733524004 447182954 415993605 453460670 50499055 648088551 986982752 907925397 315315230
output:
124 1 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 35 38 36 39 36 40 37 41 37 42 38 43 38 44 38 45 38 46 39 47 39 48 39 49 39 50 40 51 40 52 40 53 40...
result:
ok OK (10 test cases)
Test #4:
score: 0
Accepted
time: 635ms
memory: 4172kb
input:
10 1 2 3 4 5 6 7 8 9 10
output:
1 2 1 2 102 1 2 1 3 2 4 3 5 4 6 4 7 5 8 5 9 6 10 6 11 7 12 7 13 8 14 8 15 9 16 9 17 9 18 9 19 9 20 9 21 10 22 10 23 10 24 10 25 10 26 10 27 10 28 10 29 11 30 11 31 11 32 11 33 11 34 11 35 11 36 11 37 11 38 12 39 12 40 12 41 12 42 12 43 12 44 12 45 12 46 12 47 12 48 12 49 12 50 12 51 12 52 12 53 12 5...
result:
ok OK (10 test cases)
Test #5:
score: 0
Accepted
time: 292ms
memory: 3964kb
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 2 4 3 5 4 6 5 7 6 8 7 9 ...
result:
ok OK (10 test cases)
Extra Test:
score: 0
Extra Test Passed