QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#504053#7613. Inverse ProblempandapythonerWA 1ms3700kbC++236.4kb2024-08-04 04:22:502024-08-04 04:22:58

Judging History

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

  • [2024-08-04 04:22:58]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3700kb
  • [2024-08-04 04:22:50]
  • 提交

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);
                }
            }
        }
        cout << "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);
                }
            }
        }
        cout << "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

*/

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3700kb

input:

4
2
360
1
509949433

output:

dp_pref len 1
dp_suff len 0
dp_pref len 2
dp_suff len 0
dp_pref len 3
dp_suff len 0
dp_pref len 5
dp_suff len 0
dp_pref len 7
dp_suff len 0
dp_pref len 11
dp_suff len 0
dp_pref len 14
dp_suff len 1
dp_pref len 20
dp_suff len 1
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:

wrong output format Expected integer, but "dp_pref" found