QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#405486#7613. Inverse Problemucup-team3215AC ✓33089ms816240kbC++203.0kb2024-05-06 00:46:402024-05-06 00:46:40

Judging History

你现在查看的是最新测评结果

  • [2024-05-06 00:46:40]
  • 评测
  • 测评结果:AC
  • 用时:33089ms
  • 内存:816240kb
  • [2024-05-06 00:46:40]
  • 提交

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