QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#503660#7613. Inverse ProblempandapythonerTL 25326ms621652kbC++238.0kb2024-08-03 22:10:002024-08-03 22:10:01

Judging History

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

  • [2024-08-03 22:10:01]
  • 评测
  • 测评结果:TL
  • 用时:25326ms
  • 内存:621652kb
  • [2024-08-03 22:10:00]
  • 提交

answer

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

#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][maxn], dp_suff[maxn][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 (ll 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_sum = (n - 2) / 2.6;
        int max_suff_sum = n - 2 - max_pref_sum - 1;
        rep(x, n - 1) rep(y, n - 1) dp_pref[x][y] = dp_suff[x][y] = {};
        for (int val = 1; val <= n - 2; val += 1) {
            dp_pref[val][0] = { factors[val] };
            for (int sum = 1; val + sum <= n - 2 and sum <= max_pref_sum; sum += 1) {
                int sum_size = 0;
                for (int old_val = 1; old_val <= sum and old_val <= val; old_val += 1) {
                    sum_size += len(dp_pref[old_val][sum - old_val]);
                }
                dp_pref[val][sum].reserve(sum_size);
                for (int old_val = 1; old_val <= sum and old_val <= val; old_val += 1) {
                    for (auto x : dp_pref[old_val][sum - old_val]) {
                        dp_pref[val][sum].push_back(ll(x) * factors[val] % mod);
                    }
                }
                // sort(all(dp_pref[val][sum]));
                // dp_pref[val][sum].resize(unique(all(dp_pref[val][sum])) - dp_pref[val][sum].begin());
            }
        }
        auto restore_pref = [&](int val, int sum, ll x) {
            assert(find(all(dp_pref[val][sum]), x) != dp_pref[val][sum].end());
            vector<int> result;
            result.push_back(val);
            while (sum > 0) {
                int new_val = -1;
                x = x * inv_factors[val] % mod;
                for (int old_val = 1; old_val <= sum and old_val <= val; old_val += 1) {
                    if (find(all(dp_pref[old_val][sum - old_val]), x) != dp_pref[old_val][sum - old_val].end()) {
                        new_val = old_val;
                        break;
                    }
                }
                assert(new_val != -1);
                val = new_val;
                sum -= val;
                result.push_back(val);
            }
            return result;
            };
        for (int val = n - 2; val >= 1; val -= 1) {
            dp_suff[val][0] = { 1 };
            for (int sum = 1; val + sum <= n - 2 and sum <= max_suff_sum; sum += 1) {
                int sum_size = 0;
                for (int old_val = val; old_val <= sum; old_val += 1) {
                    sum_size += len(dp_suff[old_val][sum - old_val]);
                }
                dp_suff[val][sum].reserve(sum_size);
                for (int old_val = val; old_val <= sum; old_val += 1) {
                    for (auto x : dp_suff[old_val][sum - old_val]) {
                        dp_suff[val][sum].push_back(ll(x) * inv_factors[old_val] % mod);
                    }
                }
                // sort(all(dp_suff[val][sum]));
                // dp_suff[val][sum].resize(unique(all(dp_suff[val][sum])) - dp_suff[val][sum].begin());
            }
        }
        auto restore_suff = [&](int val, int sum, ll x) {
            assert(find(all(dp_suff[val][sum]), x) != dp_suff[val][sum].end());
            vector<int> result;
            while (sum > 0) {
                int new_val = -1;
                for (int old_val = val; old_val <= sum; old_val += 1) {
                    if (find(all(dp_suff[old_val][sum - old_val]), ll(x) * factors[old_val] % mod) != dp_suff[old_val][sum - old_val].end()) {
                        new_val = old_val;
                        break;
                    }
                }
                assert(new_val != -1);
                x = x * factors[new_val] % mod;
                val = new_val;
                sum -= val;
                result.push_back(val);
            }
            return result;
            };
        ll d = n * (n - 1) % mod;
        ll invd = inv(d);
        for (int pref_sum = 0; pref_sum <= max_pref_sum; pref_sum += 1) {
            for (int val = 1; pref_sum + val <= n - 2; val += 1) {
                if (pref_sum + val <= max_pref_sum) continue;
                int suff_sum = n - 2 - pref_sum - val;
                assert(suff_sum <= max_suff_sum);
                if (dp_pref[val][pref_sum].empty() or dp_suff[val][suff_sum].empty()) continue;
                rep(i, t) if (!is_solved[i]) {
                    ll biba = a[i] * invd % mod;
                    for(auto x: dp_pref[val][pref_sum]){
                        table[x] = 1;
                    }
                    for (auto y : dp_suff[val][suff_sum]) {
                        ll x = biba * y % mod;
                        if (table[x]) {
                            vector<int> degs_pref = restore_pref(val, pref_sum, x);
                            vector<int> degs_suff = restore_suff(val, 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[val][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

*/

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3724kb

input:

4
2
360
1
509949433

output:

2
1 2
5
3 1
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: 25326ms
memory: 621652kb

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
27 26
28 26
29 25
30 26
31 25
32 26
33 25
34 26
35 25
36 26
37 25
38 26
39 25
40 26
41 25
42 26
43 25
44 26
45 25
46 26
47 25
48 26
49 25
50 26
51 25
52 26
53 25
54 26
55 25
56 26
57 25
58 26
59 25
60 26
61 25
62 26
63 25
64 26
65 25
...

result:

ok OK (9 test cases)

Test #3:

score: -100
Time Limit Exceeded

input:

10
338497514
733524004
447182954
415993605
453460670
50499055
648088551
986982752
907925397
315315230

output:


result: