QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#225586 | #7613. Inverse Problem | ucup-team1209 | WA | 0ms | 104084kb | C++20 | 3.4kb | 2023-10-24 20:22:31 | 2023-10-24 20:22:32 |
Judging History
answer
#include<bits/stdc++.h>
using std::cin, std::cout;
const int N = 300;
const int mod = 1e9 + 7;
std::bitset<mod> vis;
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 = 0;i < (int) deg.size();++i) {
for(int j = 0;j < (int) 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';
}
}
}
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 + (n - i) * x <= 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 cnt, int deg, int * f, int w, auto & d, int n) {
for(int s = 1;s <= 6;++s) {
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;
}
}
}
std::vector<int> qy;
int ok[N];
int main() {
#ifdef zqj
freopen("$.in", "r", stdin);
#endif
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};
ok[i] = 1;
}
}
for(int n = 2;;++n) {
dp[0][0] = {1};
const int lim = 7;
for(int i = 1;i <= lim;i += 1) {
ins(i, n, ifac);
}
u64 val = (u64) inv[n] * inv[n - 1] % mod;
for(int i = 0;i < n;++i) {
val = val * ifac[n - 2] % mod;
}
std::vector<u64> z(t);
for(int i = 0;i < t;++i) {
z[i] = val * r[i] % mod;
}
int sdp = 0;
for(int i = 0;i <= n;++i) {
for(int j = 0;j <= n + n - 2;++j) {
int rem = n - i, deg = n + n - 2 - j;
if(dp[i][j].empty()) continue;
if(deg < rem * (lim + 1)) continue;
sdp += dp[i][j].size();
for(int x : dp[i][j]) {
vis.set(x);
}
int st[300] = {};
auto dfs = [&](auto dfs, int m, int s, int min, int prod) -> void {
if(s < min * m) return ;
if(s > (n - 1) * m) return ;
if(m == 1) {
min = s;
s = 0;
m = 0;
prod = (u64) prod * fac[n - 1 - min] % mod;
}
if(m == 0) {
for(int id = 0;id < t;++id) {
if(ok[id]) continue;
u64 q = z[id] * prod % mod;
if(vis.test(q)) {
ans[id] = std::vector<int>(st, st + rem);
push(i, j, fac, q, ans[id], n);
ok[id] = 1;
}
}
return ;
}
for(int x = min;x <= s && x < n && x * m <= s;++x) {
st[m - 1] = x;
dfs(dfs, m - 1, s - x, x, (u64) prod * fac[n - 1 - x] % mod);
}
return ;
};
dfs(dfs, rem, deg, lim + 1, 1);
for(int x : dp[i][j]) {
vis.reset(x);
}
}
}
std::cerr << n << ' ' << sdp << '\n';
clear(n);
if(std::find(ok, ok + t, 0) == ok + t || n == 125) {
break;
}
}
for(int i = 0;i < t;++i) {
// output(ans[i]);
}
std::cerr << double(clock()) / CLOCKS_PER_SEC << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 104084kb
input:
4 2 360 1 509949433
output:
result:
wrong output format Unexpected end of file - int32 expected