QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#504053 | #7613. Inverse Problem | pandapythoner | WA | 1ms | 3700kb | C++23 | 6.4kb | 2024-08-04 04:22:50 | 2024-08-04 04:22:58 |
Judging History
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