QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#224921 | #7613. Inverse Problem | ucup-team1209 | TL | 0ms | 7772kb | C++20 | 3.1kb | 2023-10-23 17:47:48 | 2023-10-23 17:47:49 |
Judging History
answer
#include<bits/stdc++.h>
using std::cin, std::cout;
const int N = 300;
const int mod = 1e9 + 7;
using u64 = unsigned long long;
int fac[N], inv[N], ifac[N];
int r[N];
std::vector<int> ans[N];
void output(std::vector<int> deg) {
cout << deg.size() << '\n';
for(int i = 1;i <= deg.size();++i) {
for(int j = 0;j < deg.size();++j) if(deg[j] == 1) {
-- deg[j];
int k = max_element(deg.begin(), deg.end()) - deg.begin();
--deg[k];
cout << j + 1 << ' ' << k + 1 << '\n';
}
}
}
struct bag {
std::vector<int> dp[N][N];
void clear(int n) {
for(int i = 0;i <= n;++i)
for(int j = 0;j <= n + n - 2;++j)
dp[i][j].clear();
}
void ins(int x, int n, int * f) {
for(int i = 0;i < n;++i) {
for(int j = 0;j + x + (n - i - 1) <= n + n - 2;++j) {
for(int w : dp[i][j]) {
dp[i + 1][j + x].push_back((u64) w * f[n - 1 - x] % mod);
}
}
}
}
void push(int l, int r, int cnt, int deg, int * f, int w, auto & d, int n) {
for(int s = l;cnt && s <= r;s += 2) {
for(;s <= deg && cnt;) {
auto & v = dp[cnt - 1][deg - s];
int nxt = (u64) w * f[n - 1 - s] % mod;
auto it = std::ranges::find(v, nxt);
if(it == v.end()) break;
d.push_back(s);
w = nxt;
cnt -= 1;
deg -= s;
}
}
}
} a[2];
int main() {
std::ios::sync_with_stdio(false), cin.tie(0);
fac[0] = ifac[0] = fac[1] = ifac[1] = inv[1] = 1;
for(int i = 2;i < N;++i) {
inv[i] = u64(mod - mod / i) * inv[mod % i] % mod;
fac[i] = (u64) fac[i - 1] * i % mod;
ifac[i] = (u64) ifac[i - 1] * inv[i] % mod;
}
int t; cin >> t;
for(int i = 0;i < t;++i) {
cin >> r[i];
if(r[i] == 1) {
ans[i] = {0};
}
}
for(int n = 2;;++n) {
a[0].dp[0][0] = {1};
a[1].dp[0][0] = {1};
for(int i = 1;i < n;i += 2) {
a[0].ins(i, n, ifac);
}
for(int i = 2;i < n;i += 2) {
a[1].ins(i, n, fac);
}
int ssize = 0;
int ssize1 = 0;
u64 su = 0;
u64 val = (u64) inv[n] * inv[n - 1] % mod;
for(int i = 0;i < n;++i) {
val = val * ifac[n - 2] % mod;
}
for(int i = 0;i <= n;++i) {
for(int k = 0;k < t;++k) {
if(ans[k].size()) continue;
for(int j = 0;j <= n + n - 2;++j) {
auto & v = a[0].dp[n - i][n + n - 2 - j];
if(!v.size()) continue;
if(!a[1].dp[i][j].size()) continue;
std::ranges::sort(v);
u64 z = val * r[k] % mod;
su += a[0].dp[i][j].size() * v.size();
ssize += a[1].dp[i][j].size();
ssize1 += v.size();
for(int w : a[1].dp[i][j]) {
u64 p = z * w % mod;
auto it = std::ranges::lower_bound(v, p);
if(it == v.end() || *it != p) continue;
a[0].push(1, n - 1, n - i, n + n - 2 - j, fac, p, ans[k], n);
a[1].push(2, n - 1, i, j, ifac, w, ans[k], n);
// std::cerr << "done " << '\n';
break;
}
if(ans[k].size()) break;
}
}
}
// std::cerr << n << ' ' << ssize << ' ' << ssize1 << ' ' << su << std::endl;
a[0].clear(n);
a[1].clear(n);
int done = 1;
for(int i = 0;i < t;++i) {
done = done && ans[i].size();
}
if(done) {
break;
}
}
for(int i = 0;i < t;++i) {
output(ans[i]);
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 7772kb
input:
4 2 360 1 509949433
output:
2 1 2 5 1 4 2 4 3 5 4 5 1 10 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 10
result:
ok OK (4 test cases)
Test #2:
score: -100
Time Limit Exceeded
input:
9 185396120 468170792 837583517 696626231 338497514 762842660 800028852 928391161 733524004