QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#276574#7613. Inverse ProblemAllTheWayNorth#ML 0ms4776kbC++143.3kb2023-12-05 22:59:282023-12-05 22:59:28

Judging History

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

  • [2023-12-05 22:59:28]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:4776kb
  • [2023-12-05 22:59:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int M = 150;
int power(int a, int b) {
    long long res = a, ans = 1;
    for (; b; b >>= 1, res = res * res % mod) if (b & 1) ans = ans * res % mod;
    return ans;
}

struct node {
    int n;
    vector <int> L[M], R[M];
    int f[M];
    void build(int N) {
        n = N;
        f[0] = 1;
        for (int i = 1; i <= n - 2; i++) f[i] = 1ll * f[i - 1] * (n - i - 1) % mod;
        L[0].push_back(1);
        R[0].push_back(1);
        int l = 1, r = n - 2;
        int suml = 1, sumr = 1;
        while (l <= r) {
            if (suml < sumr) {
                int inv = power(f[l], mod - 2);
                for (int i = 0; i + l <= n - 2; i++) {
                    for (auto j : L[i]) L[i + l].push_back(1ll * j * inv % mod), suml++;
                }
                l++;
            }
            else {
                for (int i = 0; i + r <= n - 2; i++) {
                    for (auto j : R[i]) R[i + r].push_back(1ll * j * f[r] % mod), sumr++;
                }
                r--;
            }
        }
        for (int i = 0; i <= n - 2; i++) {
            sort(L[i].begin(), L[i].end());
            sort(R[i].begin(), R[i].end());
        }
    }
    int query(int v) {
        v = 1ll * v * power(1ll * n * (n - 1) % mod, mod - 2) % mod;
        for (int i = 0; i <= n - 2; i++) {
            for (auto j : L[i]) {
                int cur = 1ll * v * j % mod;
                auto ite = lower_bound(R[n - 2 - i].begin(), R[n - 2 - i].end(), cur);
                if (ite == R[n - 2 - i].end() || *ite != cur) continue;
                printf("%d\n", n);
                printf("1 2\n");
                int p = 2, tmp = j, rst = i;
                for (int t = 1; t <= rst; t++) {
                    while (rst >= t) {
                        int nxt = 1ll * tmp * f[t] % mod;
                        auto ite = lower_bound(L[rst - t].begin(), L[rst - t].end(), nxt);
                        if (ite == L[rst - t].end() || *ite != nxt) break;
                        rst -= t, tmp = nxt;
                        for (int x = 1; x <= t; x++) printf("%d %d\n", p, p + x);
                        p += t;
                    }
                }
                assert(tmp == 1 && rst == 0);
                tmp = cur, rst = n - 2 - i;
                for (int t = 1; t <= rst; t++) {
                    while (rst >= t) {
                        int nxt = 1ll * tmp * power(f[t], mod - 2) % mod;
                        auto ite = lower_bound(R[rst - t].begin(), R[rst - t].end(), nxt);
                        if (ite == R[rst - t].end() || *ite != nxt) break;
                        rst -= t, tmp = nxt;
                        for (int x = 1; x <= t; x++) printf("%d %d\n", p, p + x);
                        p += t;
                    }
                }
                assert(tmp == 1 && rst == 0);
                return 1;
            }
        }
        return 0;
    }
} a[M];


void rmain() {
    int r;
    scanf("%d", &r);
    if (r == 1) {
        puts("1");
        return;
    }
    for (int i = 2; ; i++) {
        if (a[i].n == 0) a[i].build(i);
        if (a[i].query(r)) return;
    }
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) rmain();
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 4776kb

input:

4
2
360
1
509949433

output:

2
1 2
5
1 2
2 3
3 4
3 5
1
10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

result:

ok OK (4 test cases)

Test #2:

score: -100
Memory Limit Exceeded

input:

9
185396120
468170792
837583517
696626231
338497514
762842660
800028852
928391161
733524004

output:

14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
10 12
12 13
12 14
122
1 2
2 3
3 4
4 5
5 6
6 7
7 8
7 9
9 10
9 11
11 12
11 13
13 14
13 15
13 16
16 17
16 18
16 19
19 20
19 21
19 22
22 23
22 24
22 25
22 26
26 27
26 28
26 29
26 30
30 31
30 32
30 33
30 34
30 35
35 36
35 37
35 38
35 39
35 40
35 41
35 42
42 4...

result: