QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#504054#7613. Inverse ProblempandapythonerAC ✓32065ms207288kbC++236.4kb2024-08-04 04:23:372024-08-04 04:23:37

Judging History

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

  • [2024-08-04 04:23:37]
  • 评测
  • 测评结果：AC
  • 用时：32065ms
  • 内存：207288kb
查看
  • [2024-08-04 04:23:37]
  • 提交

answer

#ifndef LOCAL
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#endif

#include <bits/stdc++.h>

using namespace std;


using ll = long long;


#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for(int i = 0; i < n; i += 1)
#define len(a) ((int)(a).size())


const ll inf = 1e18;
mt19937 rnd(234);
const ll mod = 1e9 + 7;


ll bin_pow(ll x, ll n) {
    ll rs = 1;
    for (ll a = x, i = 1; i <= n; i *= 2, a = (a * a) % mod)
        if (n & i) rs = rs * a % mod;
    return rs;
}


ll inv(ll x) {
    ll a = bin_pow(x, mod - 2);
    assert(a * x % mod == 1);
    return a;
}


vector<pair<int, int>> restore_tree(vector<int> degs) {
    int n = len(degs);
    vector<pair<int, int>> edges;
    set<pair<int, int>> st;
    int sum = 0;
    rep(i, n) {
        sum += degs[i];
        st.insert(make_pair(degs[i], i));
    }
    assert(sum == 2 * n - 2);
    while (!st.empty()) {
        assert(len(st) >= 2);
        auto [du, u] = *st.begin();
        st.erase(st.begin());
        auto [dv, v] = *prev(st.end());
        st.erase(prev(st.end()));
        assert(du == 1);
        edges.push_back(make_pair(u, v));
        assert(st.empty() or dv > 1);
        if (dv > 1)
            st.insert(make_pair(dv - 1, v));
    }
    return edges;
}


const int maxn = 200;

vector<int> dp_pref[maxn], dp_suff[maxn];
bitset<mod> table;

int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    int t;
    cin >> t;
    vector<ll> a(t);
    rep(i, t) cin >> a[i];
    vector<bool> is_solved(t, false);
    vector<vector<pair<int, int>>> trees(t);
    rep(i, t) {
        if (a[i] == 1) {
            trees[i] = {};
            is_solved[i] = true;
        } else if (a[i] == 2) {
            trees[i] = { make_pair(0, 1) };
            is_solved[i] = true;
        }
    }
    for(int n = 3; ; n += 1) {
        if (all_of(all(is_solved), identity())) {
            break;
        }
        cerr << n << "\n";
        assert(n < maxn);
        vector<ll> factors(n - 1);
        factors[0] = 1;
        for (int i = 1; i <= n - 2; i += 1) {
            factors[i] = (ll(factors[i - 1]) * (n - 1 - i)) % mod;
        }
        vector<ll> inv_factors(n - 1);
        rep(i, n - 1) inv_factors[i] = inv(factors[i]);
        int max_pref_val = 6;
        rep(x, n - 1) dp_pref[x] = dp_suff[x] = {};
        dp_pref[0] = dp_suff[0] = { 1 };
        for(int val = 1; val <= max_pref_val; val += 1){
            for(int sum = val; sum <= n - 2; sum += 1){
                for (auto x : dp_pref[sum - val]) {
                    dp_pref[sum].push_back(x * factors[val] % mod);
                }
            }
        }
        cerr << "dp_pref len " << len(dp_pref[n - 2]) << "\n"; 
        for(int val = max_pref_val + 1; val <= n - 2; val += 1){
            for(int sum = val; sum <= n - 2; sum += 1){
                for (auto x : dp_suff[sum - val]) {
                    dp_suff[sum].push_back(x * inv_factors[val] % mod);
                }
            }
        }
        cerr << "dp_suff len " << len(dp_suff[n - 2]) << "\n";
        auto restore_pref = [&](int sum, ll x) {
            assert(find(all(dp_pref[sum]), x) != dp_pref[sum].end());
            vector<int> result;
            while (sum > 0) {
                int new_val = -1;
                for (int old_val = 1; old_val <= sum and old_val <= max_pref_val; old_val += 1) {
                    if (find(all(dp_pref[sum - old_val]), x * inv_factors[old_val] % mod) != dp_pref[sum - old_val].end()) {
                        new_val = old_val;
                        break;
                    }
                }
                assert(new_val != -1);
                sum -= new_val;
                result.push_back(new_val);
                x = x * inv_factors[new_val] % mod;
            }
            return result;
            };
        auto restore_suff = [&](int sum, ll x) {
            assert(find(all(dp_suff[sum]), x) != dp_suff[sum].end());
            vector<int> result;
            while (sum > 0) {
                int new_val = -1;
                for (int old_val = max_pref_val + 1; old_val <= sum; old_val += 1) {
                    if (find(all(dp_suff[sum - old_val]), x * factors[old_val] % mod) != dp_suff[sum - old_val].end()) {
                        new_val = old_val;
                        break;
                    }
                }
                assert(new_val != -1);
                x = x * factors[new_val] % mod;
                sum -= new_val;
                result.push_back(new_val);
            }
            return result;
            };
        ll d = n * (n - 1) % mod;
        ll invd = inv(d);
        for (int pref_sum = 0; pref_sum <= n - 2; pref_sum += 1) {
            int suff_sum = n - 2 - pref_sum;
            if (dp_pref[pref_sum].empty() or dp_suff[suff_sum].empty()) continue;
            rep(i, t) if (!is_solved[i]) {
                ll biba = a[i] * invd % mod;
                for (auto x : dp_pref[pref_sum]) {
                    table[x] = 1;
                }
                for (auto y : dp_suff[suff_sum]) {
                    ll x = biba * y % mod;
                    if (table[x]) {
                        vector<int> degs_pref = restore_pref(pref_sum, x);
                        vector<int> degs_suff = restore_suff(suff_sum, y);
                        auto degs = degs_pref;
                        for (auto f : degs_suff) {
                            degs.push_back(f);
                        }
                        assert(len(degs) <= n - 2);
                        degs.resize(n, 0);
                        for (auto& f : degs) f += 1;
                        trees[i] = restore_tree(degs);
                        is_solved[i] = true;
                        break;
                    }
                }
                for (auto x : dp_pref[pref_sum]) {
                    table[x] = 0;
                }
            }
        }
    }
    for (auto tree : trees) {
        int n = len(tree) + 1;
        cout << n << "\n";
        for (auto [u, v] : tree) {
            cout << u + 1 << " " << v + 1 << "\n";
        }
    }
    return 0;
}

/*
9
185396120
468170792
837583517
696626231
338497514
762842660
800028852
928391161
733524004

10
3
4
5
6
7
8
9
10
11
12

*/
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
2
360
1
509949433

output:

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

result:

ok OK (4 test cases)

Test #2:

score: 0
Accepted
time: 14830ms
memory: 207288kb

input:

9
185396120
468170792
837583517
696626231
338497514
762842660
800028852
928391161
733524004

output:

14
11 10
12 9
13 10
10 9
9 8
8 7
7 6
6 5
5 4
4 3
3 2
2 1
1 14
122
21 20
22 20
23 20
24 20
25 20
26 20
27 20
28 20
29 20
30 20
31 20
32 20
33 20
34 20
35 20
36 20
37 19
38 18
39 20
40 19
41 18
42 17
43 20
44 19
45 18
46 17
47 20
48 19
49 18
50 17
51 20
52 19
53 18
54 17
55 16
56 20
57 19
58 18
59 17
...

result:

ok OK (9 test cases)

Test #3:

score: 0
Accepted
time: 32065ms
memory: 206684kb

input:

10
338497514
733524004
447182954
415993605
453460670
50499055
648088551
986982752
907925397
315315230

output:

124
23 22
24 22
25 22
26 22
27 22
28 22
29 22
30 22
31 22
32 22
33 22
34 22
35 22
36 22
37 22
38 22
39 22
40 22
41 22
42 22
43 21
44 22
45 21
46 22
47 21
48 22
49 21
50 22
51 21
52 22
53 21
54 22
55 21
56 20
57 19
58 22
59 21
60 20
61 19
62 18
63 22
64 21
65 20
66 19
67 18
68 17
69 16
70 15
71 22
72...

result:

ok OK (10 test cases)

Test #4:

score: 0
Accepted
time: 3107ms
memory: 150668kb

input:

10
1
2
3
4
5
6
7
8
9
10

output:

1
2
1 2
102
16 15
17 15
18 15
19 15
20 15
21 15
22 14
23 15
24 14
25 15
26 14
27 15
28 14
29 15
30 14
31 15
32 14
33 13
34 15
35 14
36 13
37 15
38 14
39 13
40 15
41 14
42 13
43 12
44 15
45 14
46 13
47 12
48 11
49 15
50 14
51 13
52 12
53 11
54 10
55 15
56 14
57 13
58 12
59 11
60 10
61 15
62 14
63 13
...

result:

ok OK (10 test cases)

Test #5:

score: 0
Accepted
time: 925ms
memory: 136048kb

input:

10
269199917
392009324
753889928
751355133
472639410
132096559
331333826
40414701
72847302
475706026

output:

55
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
1 55
84
36 35
37 35
38 35
39 34
40 33
41...

result:

ok OK (10 test cases)

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2024-12-04 23:49:31 | OpenSource Project