結果
問題 | No.2507 Yet Another Subgraph Counting |
ユーザー |
![]() |
提出日時 | 2023-10-13 23:12:41 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 71 ms / 2,000 ms |
コード長 | 5,260 bytes |
コンパイル時間 | 4,285 ms |
コンパイル使用メモリ | 373,632 KB |
実行使用メモリ | 14,976 KB |
最終ジャッジ日時 | 2024-09-15 19:04:17 |
合計ジャッジ時間 | 6,557 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 52 |
ソースコード
#if __INCLUDE_LEVEL__ == 0#include __BASE_FILE__namespace {void solve() {int n, m;scan(n, m);vector<int> g(n);while (m--) {int i, j;scan(i, j);--i, --j;g[i] |= 1 << j;g[j] |= 1 << i;}vector<int64_t> c(1 << n);{vector f(n, vector(n, vector<int64_t>(1 << n)));for (int i : rep(n)) {f[i][i][1 << i] = 1;}for (int mask : rep(1, 1 << n)) {for (int i : bits(mask)) {for (int j : bits(mask)) {for (int k : bits(g[j] & ~mask)) {f[i][k][mask | 1 << k] += f[i][j][mask];}}}int p = popcnt(mask);if (p == 1) {c[mask] = 1;} else if (p != 2) {for (int i : bits(mask)) {for (int j : bits(g[i] & mask)) {c[mask] += f[i][j][mask];}}c[mask] /= p * 2;}}}vector<int> a(1 << n);for (int i : rep(n)) {for (int j : bits(g[i])) {if (i < j) {a[1 << i | 1 << j] = 1;}}}for (int s = 1; s < 1 << n; s *= 2) {for (int o = 0; o < 1 << n; o += s * 2) {for (int i : rep(o, o + s)) {a[i + s] += a[i];}}}vector f(n, vector<int64_t>(1 << n));for (int mask : rep(1, 1 << n)) {f[0][mask] = c[mask];int p = popcnt(mask);for (int e : rep(1, p)) {for (int sub : subsets(mask & (mask - 1))) {if (sub == 0) {break;}for (int e0 : rep(e)) {f[e][mask] += f[e0][sub] * f[e - e0 - 1][mask ^ sub] *(a[mask] - a[sub] - a[mask ^ sub]);}}f[e][mask] /= e;}}vector<int64_t> b(1 << n);for (int mask : rep(1 << n)) {for (int e : rep(popcnt(mask))) {b[mask] += f[e][mask];}}vector<int64_t> h(1 << n);h[0] = 1;for (int mask : rep(1, 1 << n)) {h[mask] += b[mask];for (int sub : subsets(mask & (mask - 1))) {if (sub == 0) {break;}h[mask] += h[sub] * b[mask ^ sub];}}print(h.back());}} // namespaceint main() {ios::sync_with_stdio(false);cin.tie(nullptr);solve();}#else // __INCLUDE_LEVEL__#include <bits/stdc++.h>using namespace std;#include <immintrin.h>__attribute__((target("bmi"))) inline int tzcnt(int64_t x) {return _tzcnt_u64(x);}__attribute__((target("bmi2"))) inline int64_t bzhi(int64_t x, int n) {return _bzhi_u64(x, n);}__attribute__((target("bmi2"))) inline int64_t pdep(int64_t x, int64_t mask) {return _pdep_u64(x, mask);}__attribute__((target("bmi2"))) inline int64_t pext(int64_t x, int64_t mask) {return _pext_u64(x, mask);}__attribute__((target("lzcnt"))) inline int lzcnt(int64_t x) {return _lzcnt_u64(x);}__attribute__((target("popcnt"))) inline int popcnt(int64_t x) {return __builtin_popcountll(x);}struct bits {int64_t x;int i;explicit bits(int64_t x) : x(x), i(tzcnt(x)) {}bits begin() const { return *this; }int end() const { return 0; }bool operator!=(int) const { return x; }void operator++() { i = tzcnt(x &= x - 1); }int operator*() const { return i; }};struct subsets {int64_t x, y;explicit subsets(int64_t x) : x(x), y(x + 1) {}subsets begin() const { return *this; }int end() const { return 0; }bool operator!=(int) const { return y; }void operator++() const {}int64_t operator*() { return y = (y - 1) & x; }};namespace std {template <class T1, class T2>istream& operator>>(istream& is, pair<T1, T2>& p) {return is >> p.first >> p.second;}template <class... Ts>istream& operator>>(istream& is, tuple<Ts...>& t) {return apply([&is](auto&... xs) -> istream& { return (is >> ... >> xs); }, t);}template <class R, enable_if_t<!is_convertible_v<R, string>>* = nullptr>auto operator>>(istream& is, R&& r) -> decltype(is >> *begin(r)) {for (auto&& e : r) {is >> e;}return is;}template <class T1, class T2>ostream& operator<<(ostream& os, const pair<T1, T2>& p) {return os << p.first << ' ' << p.second;}template <class... Ts>ostream& operator<<(ostream& os, const tuple<Ts...>& t) {auto f = [&os](const auto&... xs) -> ostream& {[[maybe_unused]] auto sep = "";((os << exchange(sep, " ") << xs), ...);return os;};return apply(f, t);}template <class R, enable_if_t<!is_convertible_v<R, string_view>>* = nullptr>auto operator<<(ostream& os, R&& r) -> decltype(os << *begin(r)) {auto sep = "";for (auto&& e : r) {os << exchange(sep, " ") << e;}return os;}} // namespace stdtemplate <class... Ts>void scan(Ts&&... xs) {(cin >> ... >> xs);}template <class... Ts>void print(Ts&&... xs) {cout << tie(xs...) << '\n';}inline auto rep(int l, int r) { return views::iota(min(l, r), r); }inline auto rep(int n) { return rep(0, n); }inline auto rep1(int l, int r) { return rep(l, r + 1); }inline auto rep1(int n) { return rep(1, n + 1); }inline auto per(int l, int r) { return rep(l, r) | views::reverse; }inline auto per(int n) { return per(0, n); }inline auto per1(int l, int r) { return per(l, r + 1); }inline auto per1(int n) { return per(1, n + 1); }inline auto len = ranges::ssize;#endif // __INCLUDE_LEVEL__