結果
問題 | No.2507 Yet Another Subgraph Counting |
ユーザー |
|
提出日時 | 2023-10-23 12:24:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 310 ms / 2,000 ms |
コード長 | 6,069 bytes |
コンパイル時間 | 2,352 ms |
コンパイル使用メモリ | 208,212 KB |
最終ジャッジ日時 | 2025-02-17 13:17:27 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 52 |
ソースコード
#include <bits/stdc++.h>using namespace std;struct io_setup {io_setup() {ios_base::sync_with_stdio(false);cin.tie(NULL);cout << fixed << setprecision(15);}} io_setup;template <typename T>void print(const vector<T> &v, T x = 0) {int n = v.size();for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' ');if (v.empty()) cout << '\n';}constexpr int MOD = 998244353;template <typename T>void fast_zeta_transform(vector<T> &a, bool upper) {int n = a.size();assert((n & (n - 1)) == 0);for (int i = 1; i < n; i <<= 1) {for (int j = 0; j < n; j++) {if (!(j & i)) {if (upper) {a[j] += a[j | i];} else {a[j | i] += a[j];}}}}}template <typename T>void fast_mobius_transform(vector<T> &a, bool upper) {int n = a.size();assert((n & (n - 1)) == 0);for (int i = 1; i < n; i <<= 1) {for (int j = 0; j < n; j++) {if (!(j & i)) {if (upper) {a[j] -= a[j | i];} else {a[j | i] -= a[j];}}}}}template <typename T>void fast_hadamard_transform(vector<T> &a, bool inverse = false) {int n = a.size();assert((n & (n - 1)) == 0);for (int i = 1; i < n; i <<= 1) {for (int j = 0; j < n; j++) {if (!(j & i)) {T x = a[j], y = a[j | i];a[j] = x + y, a[j | i] = x - y;}}}if (inverse) {T inv = T(1) / T(n);for (auto &e : a) e *= inv;}}template <typename T>vector<T> bitwise_and_convolve(vector<T> a, vector<T> b) {int n = a.size();assert((int)b.size() == n && (n & (n - 1)) == 0);fast_zeta_transform(a, true), fast_zeta_transform(b, true);for (int i = 0; i < n; i++) a[i] *= b[i];fast_mobius_transform(a, true);return a;}template <typename T>vector<T> bitwise_or_convolve(vector<T> a, vector<T> b) {int n = a.size();assert((int)b.size() == n && (n & (n - 1)) == 0);fast_zeta_transform(a, false), fast_zeta_transform(b, false);for (int i = 0; i < n; i++) a[i] *= b[i];fast_mobius_transform(a, false);return a;}template <typename T>vector<T> bitwise_xor_convolve(vector<T> a, vector<T> b) {int n = a.size();assert((int)b.size() == n && (n & (n - 1)) == 0);fast_hadamard_transform(a), fast_hadamard_transform(b);for (int i = 0; i < n; i++) a[i] *= b[i];fast_hadamard_transform(a, true);return a;}template <typename T>vector<T> subset_convolve(const vector<T> &a, const vector<T> &b) {int n = a.size();assert((int)b.size() == n && (n & (n - 1)) == 0);int k = __builtin_ctz(n);vector<vector<T>> A(k + 1, vector<T>(n, 0)), B(k + 1, vector<T>(n, 0)), C(k + 1, vector<T>(n, 0));for (int i = 0; i < n; i++) {int t = __builtin_popcount(i);A[t][i] = a[i], B[t][i] = b[i];}for (int i = 0; i <= k; i++) fast_zeta_transform(A[i], false), fast_zeta_transform(B[i], false);for (int i = 0; i <= k; i++) {for (int j = 0; j <= k - i; j++) {for (int l = 0; l < n; l++) C[i + j][l] += A[i][l] * B[j][l];}}for (int i = 0; i <= k; i++) fast_mobius_transform(C[i], false);vector<T> c(n);for (int i = 0; i < n; i++) c[i] = C[__builtin_popcount(i)][i];return c;}template <typename T>vector<T> multiple_subset_convolve(const vector<T> &a) {int n = a.size();assert((n & (n - 1)) == 0);assert(a[0] == T(0));vector<T> b(1, 1);for (int k = 1; k < n; k <<= 1) {vector<T> a_sub(begin(a) + k, begin(a) + k * 2);vector<T> b_sub = subset_convolve(a_sub, b);b.insert(end(b), begin(b_sub), end(b_sub));}return b;}using ll = long long;int main() {int N, M;cin >> N >> M;vector<int> es(N, 0);for (int i = 0; i < M; i++) {int u, v;cin >> u >> v;u--, v--;es[u] |= 1 << v;es[v] |= 1 << u;}auto cut_size = [&](int S, int T) {int ret = 0;for (int i = 0; i < N; i++) {if (!(S >> i & 1)) continue;ret += __builtin_popcount(es[i] & T);}return ret;};vector<vector<ll>> dp(N, vector<ll>(1 << N, 0));for (int s = 0; s < N; s++) {vector<vector<ll>> dp1(1 << N, vector<ll>(N, 0));dp1[1 << s][s] = 1;for (int S = 0; S < (1 << N); S++) {for (int t = 0; t < N; t++) {if (__builtin_popcount(S) != 2 && (es[t] >> s) & 1) dp[0][S] += dp1[S][t];for (int nt = s; nt < N; nt++) {if ((S >> nt) & 1) continue;if (!(es[t] >> nt & 1)) continue;int nS = S | (1 << nt);dp1[nS][nt] += dp1[S][t];}}}dp[0][1 << s] += 1;}for (int S = 0; S < (1 << N); S++) {if (__builtin_popcount(S) >= 3) {assert(dp[0][S] % 2 == 0);dp[0][S] /= 2;}}for (int S = 1; S < (1 << N); S++) {for (int X = (S - 1) & S; X > 0; X--, X &= S) {int Y = S & ~X;if (X < Y) continue;int c = cut_size(X, Y);for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (i + j < N - 1) dp[i + j + 1][S] += dp[i][X] * dp[j][Y] * c;}}}for (int i = 1; i < N; i++) {assert(dp[i][S] % i == 0);dp[i][S] /= i;}}// for (int i = 0; i < N; i++) print(dp[i]);vector<ll> a(1 << N, 0);for (int S = 0; S < (1 << N); S++) {for (int i = 0; i < N; i++) a[S] += dp[i][S];}// print(a);auto b = multiple_subset_convolve(a);cout << b.back() << '\n';}