QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #225443 | #7613. Inverse Problem | ucup-team1209 | Compile Error | / | / | C++20 | 3.2kb | 2023-10-24 17:33:52 | 2023-10-24 17:33:53 |
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 = 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 += 1) {
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};
int lim = std::max(n / 18, 1);
for(int i = 1;i <= lim;i += 1) {
a[0].ins(i, n, ifac);
}
for(int i = lim + 1;i < n;i += 1) {
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 x : vis) vis.set(p);
for(int w : a[1].dp[i][j]) {
u64 p = z * w % mod;
if(!vis.test(p)) continue;
a[0].push(1, lim, n - i, n + n - 2 - j, fac, p, ans[k], n);
a[1].push(lim + 1, n - 1, i, j, ifac, w, ans[k], n);
// std::cerr << "done " << '\n';
break;
}
for(int x : vis) vis.reset(p);
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]);
}
}
Details
answer.code: In function ‘int main()’:
answer.code:98:53: error: no matching function for call to ‘begin(std::bitset<1000000007>&)’
98 | for(int x : vis) vis.set(p);
| ^~~
In file included from /usr/include/c++/11/bits/algorithmfwd.h:39,
from /usr/include/c++/11/bits/stl_algo.h:60,
from /usr/include/c++/11/string:52,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from answer.code:1:
/usr/include/c++/11/initializer_list:90:5: note: candidate: ‘template<class _Tp> constexpr const _Tp* std::begin(std::initializer_list<_Tp>)’
90 | begin(initializer_list<_Tp> __ils) noexcept
| ^~~~~
/usr/include/c++/11/initializer_list:90:5: note: template argument deduction/substitution failed:
answer.code:98:53: note: ‘std::bitset<1000000007>’ is not derived from ‘std::initializer_list<_Tp>’
98 | for(int x : vis) vis.set(p);
| ^~~
In file included from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from answer.code:1:
/usr/include/c++/11/bits/range_access.h:51:5: note: candidate: ‘template<class _Container> constexpr decltype (__cont.begin()) std::begin(_Container&)’
51 | begin(_Container& __cont) -> decltype(__cont.begin())
| ^~~~~
/usr/include/c++/11/bits/range_access.h:51:5: note: template argument deduction/substitution failed:
/usr/include/c++/11/bits/range_access.h: In substitution of ‘template<class _Container> constexpr decltype (__cont.begin()) std::begin(_Container&) [with _Container = std::bitset<1000000007>]’:
answer.code:98:18: required from here
/usr/include/c++/11/bits/range_access.h:51:50: error: ‘class std::bitset<1000000007>’ has no member named ‘begin’
51 | begin(_Container& __cont) -> decltype(__cont.begin())
| ~~~~~~~^~~~~
/usr/include/c++/11/bits/range_access.h:61:5: note: candidate: ‘template<class _Container> constexpr decltype (__cont.begin()) std::begin(const _Container&)’
61 | begin(const _Container& __cont) -> decltype(__cont.begin())
| ^~~~~
/usr/include/c++/11/bits/range_access.h:61:5: note: template argument deduction/substitution failed:
/usr/include/c++/11/bits/range_access.h: In substitution of ‘template<class _Container> constexpr decltype (__cont.begin()) std::begin(const _Container&) [with _Container = std::bitset<1000000007>]’:
answer.code:98:18: required from here
/usr/include/c++/11/bits/range_access.h:61:56: error: ‘const class std::bitset<1000000007>’ has no member named ‘begin’
61 | begin(const _Container& __cont) -> decltype(__cont.begin())
| ~~~~~~~^~~~~
/usr/include/c++/11/bits/range_access.h:90:5: note: candidate: ‘template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::begin(_Tp (&)[_Nm])’
90 | begin(_Tp (&__arr)[_Nm]) noexcept
| ^~~~~
/usr/include/c++/11/bits/range_access.h:90:5: note: template argument deduction/substitution failed:
answer.code:98:53: note: mismatched types ‘_Tp [_Nm]’ and ‘std::bitset<1000000007>’
98 | for(int x : vis) vis.set(p);
| ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:95,
from answer.code:1:
/usr/include/c++/11/valarray:1214:5: note: candidate: ‘template<class _Tp> _Tp* std::begin(std::valarray<_Tp>&)’
1214 | begin(valarray<_Tp>& __va)
| ^~~~~
/usr/include/c++/11/valarray:1214:5: note: template argument deduction/substitution failed:
answer.code:98:53: note: ‘std::bitset<1000000007>’ is not derived from ‘std::valarray<_Tp>’
98 | for(int x : vis) vis.set(p);
| ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:95,
...