#924479 (C++17) No.2507 Yet Another Subgraph Counting

提出ソース

結果

問題	No.2507 Yet Another Subgraph Counting
ユーザー	hashiryo
提出日時	2023-10-30 19:10:43
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	30 ms / 2,000 ms
コード長	19,538 bytes
コンパイル時間	2,813 ms
コンパイル使用メモリ	217,312 KB
実行使用メモリ	14,976 KB
最終ジャッジ日時	2023-10-30 19:10:49
合計ジャッジ時間	4,889 ms
ジャッジサーバーID （参考情報）	judge15 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	2 ms 4,348 KB
testcase_03	AC	2 ms 4,348 KB
testcase_04	AC	2 ms 4,348 KB
testcase_05	AC	2 ms 4,348 KB
testcase_06	AC	2 ms 4,348 KB
testcase_07	AC	2 ms 4,348 KB
testcase_08	AC	2 ms 4,348 KB
testcase_09	AC	2 ms 4,348 KB
testcase_10	AC	2 ms 4,348 KB
testcase_11	AC	2 ms 4,348 KB
testcase_12	AC	2 ms 4,348 KB
testcase_13	AC	2 ms 4,348 KB
testcase_14	AC	2 ms 4,348 KB
testcase_15	AC	2 ms 4,348 KB
testcase_16	AC	2 ms 4,348 KB
testcase_17	AC	3 ms 4,348 KB
testcase_18	AC	2 ms 4,348 KB
testcase_19	AC	2 ms 4,348 KB
testcase_20	AC	2 ms 4,348 KB
testcase_21	AC	2 ms 4,348 KB
testcase_22	AC	2 ms 4,348 KB
testcase_23	AC	2 ms 4,348 KB
testcase_24	AC	2 ms 4,348 KB
testcase_25	AC	4 ms 4,348 KB
testcase_26	AC	12 ms 10,364 KB
testcase_27	AC	2 ms 4,348 KB
testcase_28	AC	3 ms 4,348 KB
testcase_29	AC	2 ms 4,348 KB
testcase_30	AC	12 ms 10,364 KB
testcase_31	AC	29 ms 14,972 KB
testcase_32	AC	30 ms 14,972 KB
testcase_33	AC	3 ms 4,348 KB
testcase_34	AC	2 ms 4,348 KB
testcase_35	AC	2 ms 4,348 KB
testcase_36	AC	2 ms 4,348 KB
testcase_37	AC	30 ms 14,972 KB
testcase_38	AC	30 ms 14,976 KB
testcase_39	AC	30 ms 14,972 KB
testcase_40	AC	30 ms 14,972 KB
testcase_41	AC	29 ms 14,972 KB
testcase_42	AC	29 ms 14,976 KB
testcase_43	AC	12 ms 10,364 KB
testcase_44	AC	29 ms 14,972 KB
testcase_45	AC	3 ms 4,348 KB
testcase_46	AC	2 ms 4,348 KB
testcase_47	AC	29 ms 14,972 KB
testcase_48	AC	2 ms 4,348 KB
testcase_49	AC	29 ms 14,972 KB
testcase_50	AC	2 ms 4,348 KB
testcase_51	AC	12 ms 10,364 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
// clang-format off
std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,const __int128_t &v){if(!v)os<<"0";__int128_t tmp=v<0?(os<<"-",-v):v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}
std::ostream&operator<<(std::ostream&os,const __uint128_t &v){if(!v)os<<"0";__uint128_t tmp=v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}
#define checkpoint() (void(0))
#define debug(...) (void(0))
#define debugArray(x,n) (void(0))
#define debugMatrix(x,h,w) (void(0))
// clang-format on
template <unsigned short MAX_N= 21> struct SetPowerSeries {
#define SUBSET_REP(i, j, n) \
 for (int _= (n); _>>= 1;) \
  for (int __= 0, _2= _ << 1; __ < (n); __+= _2) \
   for (int j= __, i= j | _, ___= i; j < ___; ++j, ++i)
 template <typename T> static inline void ranked_zeta_tr(const T f[], T ret[][MAX_N + 1], const int sz) {
  for (int S= sz, c; S--;) ret[S][c= __builtin_popcount(S)]= f[S], std::fill_n(ret[S], c, 0);
  SUBSET_REP(S, U, sz)
  for (int d= __builtin_popcount(S); d--;) ret[S][d]+= ret[U][d];
 }
 template <typename T> static inline void conv_na(const T f[], const T g[], T ret[], const int sz) {
  for (int s= sz, t; s--;)
   for (ret[t= s]= f[s] * g[0]; t; --t&= s) ret[s]+= f[s ^ t] * g[t];
 }
 template <typename T> static inline void conv_tr(const T f[], const T g[], T ret[], const int sz) {
  static T F[1 << MAX_N][MAX_N + 1], G[1 << MAX_N][MAX_N + 1];
  T tmp[MAX_N + 1];
  ranked_zeta_tr(f, F, sz), ranked_zeta_tr(g, G, sz);
  const int n= __builtin_ctz(sz);
  for (int S= sz, c, d, e, bg; S--;) {
   c= __builtin_popcount(S), bg= std::min(2 * c, n);
   for (d= bg; d >= c; d--)
    for (tmp[d]= 0, e= d - c; e <= c; ++e) tmp[d]+= F[S][e] * G[S][d - e];
   for (d= bg; d >= c; d--) F[S][d]= tmp[d];
  }
  SUBSET_REP(S, U, sz)
  for (int c= __builtin_popcount(U), d= std::min(2 * c, n); d > c; d--) F[S][d]-= F[U][d];
  for (int S= sz; S--;) ret[S]= F[S][__builtin_popcount(S)];
 }
 template <typename T, class F> static inline void onconv_na(const T g[], T ret[], const F &phi, const int sz) {
  for (int s= 1, t; s < sz; phi(s, ret[s]), ++s)
   for (ret[t= s]= 0; t; --t&= s) ret[s]+= ret[s ^ t] * g[t];
 }
 template <typename T, class F> static inline void onconv_tr(const T g[], T ret[], const F &phi, const int sz) {
  static T G[1 << MAX_N][MAX_N + 1], mat[MAX_N + 1][1 << MAX_N];
  const int n= __builtin_ctz(sz);
  ranked_zeta_tr(g, G, sz), std::fill_n(mat[0], sz, ret[0]);
  for (int d= n; d; d--) std::fill_n(mat[d], sz, 0);
  for (int I= sz; I>>= 1;) phi(I, mat[1][I]= ret[0] * g[I]);
  for (int d= 2; d <= n; ++d) {
   SUBSET_REP(S, U, sz) mat[d - 1][S]+= mat[d - 1][U];
   for (int S= sz; S--;)
    if (int c= __builtin_popcount(S); c <= d && d <= 2 * c)
     for (int e= d; e--;) mat[d][S]+= mat[e][S] * G[S][d - e];
   SUBSET_REP(S, U, sz) mat[d][S]-= mat[d][U];
   for (int S= sz; S--;) __builtin_popcount(S) == d ? phi(S, mat[d][S]), 0 : (mat[d][S]= 0);
  }
  for (int S= sz; --S;) ret[S]= mat[__builtin_popcount(S)][S];
 }
public:
 template <typename T>  // O(n 2^n)
 static inline void subset_sum(std::vector<T> &f) {
  SUBSET_REP(S, U, f.size()) f[S]+= f[U];
 }
 template <typename T>  // O(n 2^n)
 static inline void subset_sum_inv(std::vector<T> &f) {
  SUBSET_REP(S, U, f.size()) f[S]-= f[U];
 }
 template <class T>  // O(n^2 2^n)
 static inline std::vector<T> convolve(const std::vector<T> &f, const std::vector<T> &g) {
  const int sz= f.size(), n= __builtin_ctz(sz);
  std::vector<T> ret(sz);
  if (n <= 10) return conv_na(f.data(), g.data(), ret.data(), sz), ret;
  assert(sz == 1 << n && sz == g.size());
  return conv_tr(f.data(), g.data(), ret.data(), sz), ret;
 }
 // f(S) = φ_S ( Σ_{T⊊S} f(T)g(S/T) )
 template <class T, class F= void (*)(int, T &)>  // O(n^2 2^n)
 static inline std::vector<T> semi_relaxed_convolve(
     const std::vector<T> &g, T init, const F &phi= [](int, T &) {}) {
  const int sz= g.size(), n= __builtin_ctz(sz);
  std::vector<T> ret(sz);
  ret[0]= init;
  if (n <= 12) return onconv_na(g.data(), ret.data(), phi, sz), ret;
  assert(sz == 1 << n);
  return onconv_tr(g.data(), ret.data(), phi, sz), ret;
 }
 // f(S) = φ_S ( Σ_{∅≠T⊊S & (T<(S/T) as binary numbers) } f(T)f(S/T) )
 template <class T, class F>  // O(n^2 2^n)
 static inline std::vector<T> self_relaxed_convolve(int n, const F &phi) {
  assert(__builtin_popcount(n) == 1);
  int I= 1, ed= std::min(1 << 13, n);
  std::vector<T> ret(n, 0);
  for (int s, t, u= 1; I < ed; I<<= 1)
   for (t= s= 0; s < I; phi(u, ret[u]), t= ++s, ++u)
    for (ret[u]= 0; t; --t&= s) ret[u]+= ret[u ^ t] * ret[t];
  T *h= ret.data();
  for (; I < n; I<<= 1)
   phi(I, ret[I]), onconv_tr(
                       h, h + I, [&](int s, T &x) { phi(s | I, x); }, I);
  return ret;
 }
 // F(f) : F[i] is coefficient of EGF ( = F^{(i)}(0) )
 // "f[∅] = 0" is required.
 template <class T, class EGF>  // O(n^2 2^n)
 static inline std::vector<T> composite(const std::vector<T> &f, const EGF &F) {
  const int sz= f.size(), m= __builtin_ctz(sz), sz2= sz >> 1;
  assert(sz == 1 << m), assert(f.at(0) == 0);
  std::vector<T> ret(sz);
  T *h= ret.data() + sz;
  const T *g= f.data();
  for (int i= 0; i <= m; ++i) ret[sz - (1 << i)]= F[m - i];
  int l= 1, ed= std::min(sz, 1 << 11), j;
  for (; l < ed; l<<= 1)
   for (j= sz2; j >= l; j>>= 1) conv_na(h - j, g + l, h - j - j + l, l);
  for (; l < sz; l<<= 1)
   for (j= sz2; j >= l; j>>= 1) conv_tr(h - j, g + l, h - j - j + l, l);
  return ret;
 }
 // exp(f) : "f[∅] = 0" is required.
 template <class T>  // O(n^2 2^n)
 static inline std::vector<T> exp(const std::vector<T> &f) {
  const int sz= f.size();
  assert(!(sz & (sz - 1))), assert(f.at(0) == 0);
  T h[sz];
  const T *g= f.data();
  int l= 1, ed= std::min(sz, 1 << 11);
  for (h[0]= 1; l < ed; l<<= 1) conv_na(h, g + l, h + l, l);
  for (; l < sz; l<<= 1) conv_tr(h, g + l, h + l, l);
  return std::vector<T>(h, h + sz);
 }
 // log(f) : "f[∅] = 1" is required.
 template <class T>  // O(n^2 2^n)
 static inline std::vector<T> log(const std::vector<T> &f) {
  const int sz= f.size();
  assert(!(sz & (sz - 1))), assert(f.at(0) == T(1));
  int I= 2, ed= std::min(sz, 1 << 13);
  T h[sz];
  const T *g= f.data();
  for (std::copy_n(g, ed, h); I < ed; I<<= 1)
   for (int s= 1, u= s | I; s < I; ++s, ++u)
    for (int t= s; t; --t&= s) h[u]-= h[u ^ t] * f[t];
  for (; I < sz; I<<= 1)
   h[I]= g[I], onconv_tr(
                   g, h + I, [&](int s, T &x) { x= g[I | s] - x; }, I);
  return h[0]= 0, std::vector<T>(h, h + sz);
 }
 // f^k
 template <class T>  // O(n^2 2^n)
 static inline std::vector<T> pow(std::vector<T> f, uint64_t k) {
  const int sz= f.size(), n= __builtin_ctz(sz);
  assert(sz == 1 << n);
  T F[MAX_N + 1]= {1}, pw= 1, bs= f[0];
  int i= 1, ed= std::min<uint64_t>(n, k);
  for (; i <= ed; ++i) F[i]= F[i - 1] * (k - i + 1);
  for (auto e= k - --i; e; e>>= 1, bs*= bs)
   if (e & 1) pw*= bs;
  for (; i >= 0; --i, pw*= f[0]) F[i]*= pw;
  return f[0]= 0, composite(f, F);
 }
 // P(f), P is polynomial
 template <class T> static inline std::vector<T> polynomial_composite(std::vector<T> f, std::vector<T> P) {
  const int sz= f.size(), n= __builtin_ctz(sz);
  assert(sz == 1 << n);
  T F[MAX_N + 1]= {};
  int e= P.size();
  if (!e) return std::vector<T>(sz);
  for (int j= 0;; ++j, --e) {
   for (int i= e; i--;) (F[j]*= f[0])+= P[i];
   if (j == n || e == 1) break;
   for (int i= 1; i < e; ++i) P[i - 1]= P[i] * i;
  }
  return f[0]= 0, composite(f, F);
 }
 // {[X^{[n]}]f^k/k!} for k=0,1,...,n
 template <class T>  // O(n^2 2^n)
 static inline std::vector<T> egf(std::vector<T> f) {
  static constexpr int M= 1 << 11;
  const int sz= f.size(), n= __builtin_ctz(sz), sz4= sz >> 2;
  assert(sz == 1 << n);
  if (n == 1) return {0, f[1]};
  int l= sz4, m;
  T *in= f.data() + l, *dp= in + l, tmp[sz4 / 2], *dp2;
  for (int s; l > M; conv_tr(dp, in, dp, l), in-= (l>>= 1))
   for (m= sz4; dp2= dp + (m - l), m > l; m>>= 1)
    for (s= l, conv_tr(dp2 + m - l, in, tmp, l); s--;) dp2[s]+= tmp[s];
  for (int s; l; conv_na(dp, in, dp, l), in-= (l>>= 1))
   for (m= sz4; dp2= dp + (m - l), m > l; m>>= 1)
    for (s= l, conv_na(dp2 + m - l, in, tmp, l); s--;) dp2[s]+= tmp[s];
  std::vector<T> ret(n + 1, 0);
  for (int i= n + 1; --i;) ret[i]= dp[(1 << (n - i)) - 1];
  return ret;
 }
 // {[X^{[n]}]g*f^k/k!} for k=0,1,...,n
 template <class T>  // O(n^2 2^n)
 static inline std::vector<T> egf(const std::vector<T> &f, std::vector<T> g) {
  static constexpr int M= 1 << 11;
  const int sz= f.size(), n= __builtin_ctz(sz), sz2= sz >> 1, sz4= sz >> 2;
  assert(sz == 1 << n), assert(sz == (int)g.size());
  if (n == 1) return {g[1], f[1] * g[0] + f[0] * g[1]};
  int l= sz2, m;
  const T *in= f.data() + sz2;
  T *dp= g.data(), tmp[sz2 / 2], *dp2;
  for (int s; l > M; conv_tr(dp, in, dp, l), in-= (l>>= 1))
   for (m= sz2; dp2= dp + (m - l), m > l; m>>= 1)
    for (s= l, conv_tr(dp2 + m - l, in, tmp, l); s--;) dp2[s]+= tmp[s];
  for (int s; l; conv_na(dp, in, dp, l), in-= (l>>= 1))
   for (m= sz2; dp2= dp + (m - l), m > l; m>>= 1)
    for (s= l, conv_na(dp2 + m - l, in, tmp, l); s--;) dp2[s]+= tmp[s];
  std::vector<T> ret(n + 1);
  for (int i= n + 1; i--;) ret[i]= dp[(1 << (n - i)) - 1];
  return ret;
 }
#undef SUBSET_REP
};
template <unsigned short MAX_V= 21> class UndirectedGraphSetPowerSeries {
 using SPS= SetPowerSeries<MAX_V>;
 template <class T> using sps= std::vector<T>;
 template <class T> using poly= std::vector<T>;
 const unsigned V, sz;
 unsigned adj[MAX_V][MAX_V]= {0}, edge[MAX_V]= {0};
 template <class T> static inline T pow(T x, int k) {
  for (T ret(1);; x*= x)
   if (k & 1 ? ret*= x : 0; !(k>>= 1)) return ret;
 }
 template <class F> inline void bfs(int s, const F &f) const {
  for (int t= s, u, j; t;)
   for (f(u= 1 << __builtin_ctz(t)); u;) j= __builtin_ctz(u), t^= 1 << j, u^= 1 << j, u|= edge[j] & t;
 }
public:
 UndirectedGraphSetPowerSeries(int n): V(n), sz(1 << V) {}
 UndirectedGraphSetPowerSeries(const std::vector<std::vector<int>> &g): V(g.size()), sz(1 << V) {
  for (int i= V; i--;)
   for (int j= i; j--;) assert(g[i][j] == g[j][i]);
  for (int i= V; i--;)
   for (int j= V; j--;) adj[i][j]= g[i][j];
  for (int i= V; i--;)
   for (int j= V; j--;) edge[i]|= !(!(adj[i][j])) << j;
 }
 int *operator[](int u) const { return adj[u]; }
 void add_edge(int u, int v, int cnt= 1) {
  adj[u][v]= (adj[v][u]+= cnt), edge[u]|= (1 << v), edge[v]|= (1 << u);
  if (!(adj[u][v])) edge[u]^= (1 << v), edge[v]^= (1 << u);
 }
 template <class T> static inline sps<T> space_size(const sps<int> &rank) {
  sps<T> ret(rank.size());
  for (int s= rank.size(); s--;) ret[s]= pow<T>(2, rank[s]);
  return ret;
 }
 template <class T, class G> static inline void transform(sps<T> &f, const G &g) {
  const int sz2= f.size() / 2;
  sps<T> tmp(sz2);
  for (int I= sz2; I; I>>= 1) {
   for (int t= 0; t < sz2; t+= I)
    for (int u= I, t2= t << 1; u--;) tmp[t | u]= f[t2 | I | u];
   tmp= g(tmp);
   for (int t= 0; t < sz2; t+= I)
    for (int u= I, t2= t << 1; u--;) f[t2 | I | u]= tmp[t | u];
  }
 }
 template <class T>  // O(V^3 2^V)
 static inline void connect_to_biconnect(sps<T> &f) {
  transform(f, SPS::template log<T>);
 }
 template <class T>  // O(V^3 2^V)
 static inline void biconnect_to_connect(sps<T> &f) {
  transform(f, SPS::template exp<T>);
 }
 template <class T>  // O(V 2^V)
 inline void loop_ignored_to_loop_permitted(sps<T> &f) const {
  auto tmp= space_size<T>(loop_size());
  for (int s= sz; s--;) f[s]*= tmp[s];
 }
 inline sps<int> edge_space_rank() const {  // O(V 2^V)
  sps<int> ret(sz, 0);
  for (int i= V; i--;)
   for (int j= i + 1; j--;) ret[(1 << i) | (1 << j)]= adj[i][j];
  return SPS::subset_sum(ret), ret;
 }
 inline sps<int> loop_size() const {  // O(V 2^V)
  sps<int> ret(sz, 0);
  for (int i= V; i--;) ret[(1 << i)]= adj[i][i];
  return SPS::subset_sum(ret), ret;
 }
 inline sps<int> loop_ignored_edge_space_rank() const {  // O(V 2^V)
  sps<int> ret(sz, 0);
  for (int i= V; i--;)
   for (int j= i; j--;) ret[(1 << i) | (1 << j)]= adj[i][j];
  return SPS::subset_sum(ret), ret;
 }
 inline sps<int> connected_component_num() const {  // O(V 2^V)
  sps<int> ret(sz, 0);
  for (int s= sz; s--;) bfs(s, [&](int) { ret[s]++; });
  return ret;
 }
 inline sps<int> cycle_space_rank() const {  // O(V 2^V)
  sps<int> e= edge_space_rank(), k= connected_component_num(), ret(sz, 0);
  for (int s= sz; s--;) ret[s]= e[s] + k[s] - __builtin_popcount(s);
  return ret;
 }
 template <class T>  // O(V 2^V)
 inline sps<T> edge_space_size() const {
  return space_size<T>(edge_space_rank());
 }
 template <class T>  // O(V 2^V)
 inline sps<T> loop_ignored_edge_space_size() const {
  return space_size<T>(loop_ignored_edge_space_rank());
 }
 template <class T>  // O(V 2^V)
 inline sps<T> cycle_space_size() const {
  return space_size<T>(cycle_space_rank());
 }
 template <class T>  // O(V^2 2^V)
 inline sps<T> connected_graph_num() const {
  return SPS::log(edge_space_size<T>());
 }
 template <class T>  // O(V^2 2^V)
 inline sps<T> loop_ignored_connected_graph_num() const {
  return SPS::log(loop_ignored_edge_space_size<T>());
 }
 template <class T>  // O(V^2 2^V)
 inline sps<T> euler_graph_num() const {
  return SPS::log(cycle_space_size<T>());
 }
 template <class T>  // O(V^2 2^V)
 inline sps<T> connected_biparate_graph_num() const {
  sps<T> tmp= edge_space_size<T>(), ret(sz, 1);
  for (int s= sz; s--;) ret[s]/= tmp[s];
  ret= SPS::convolve(ret, ret);
  for (int s= sz; s--;) ret[s]*= tmp[s];
  ret= SPS::log(ret);
  for (int s= sz; s--;) ret[s]/= 2;
  return ret;
 }
 template <class T>  // O(V^3 2^V)
 inline sps<T> loop_ignored_biconnected_graph_num() const {
  auto ret= loop_ignored_connected_graph_num<T>();
  return connect_to_biconnect(ret), ret;
 }
 template <class T>  // O(V^3 2^V)
 inline sps<T> biconnected_graph_num() const {
  auto ret= loop_ignored_biconnected_graph_num<T>();
  return loop_ignored_to_loop_permitted(ret), ret;
 }
 template <class T>  // O(V^2 2^V)
 inline sps<T> spanning_tree_num() const {
  sps<int> e= edge_space_rank();
  sps<T> ret= {0, 1};
  ret.reserve(sz);
  for (int I= 2; I < sz; I<<= 1) {
   sps<T> g(ret);
   for (int s= I; --s;) g[s]*= e[s | I] - e[s] - e[I];
   g= SPS::exp(g);
   std::copy(g.begin(), g.end(), std::back_inserter(ret));
  }
  return ret;
 }
 template <class T>  // O(V^2 2^V)
 inline sps<T> forest_num() const {
  return SPS::exp(spanning_tree_num<T>());
 }
 template <class T>  // O(V^2 2^V)
 inline sps<T> rooted_spanning_tree_num() const {
  auto ret= spanning_tree_num<T>();
  for (int s= sz; s--;) ret[s]*= __builtin_popcount(s);
  return ret;
 }
 template <class T>  // O(V^2 2^V)
 inline sps<T> rooted_forest_num() const {
  return SPS::exp(rooted_spanning_tree_num<T>());
 }
 template <class T>  // O(V^2 2^V)
 inline sps<T> cycle_graph_num() const {
  T dp[sz][V - 1];
  sps<T> ret(sz, 0);
  for (int i= V, I= sz; I>>= 1, --i;) {
   for (int s= I; --s;) std::fill_n(dp[s], i, 0);
   for (int j= i; j--;) dp[1 << j][j]= adj[i][j];
   for (int s= 1; s < I; s++)
    for (int t= s, j, u, r, k; t; ret[s | I]+= dp[s][j] * adj[j][i])
     for (t^= 1 << (j= __builtin_ctz(t)), u= r= s ^ (1 << j); u; dp[s][j]+= dp[r][k] * adj[k][j]) u^= 1 << (k= __builtin_ctz(u));
  }
  for (int i= V; i--;)
   for (int j= i; j--;) ret[(1 << i) | (1 << j)]-= adj[i][j];
  for (int s= sz; --s;) ret[s]/= 2;
  for (int i= V; i--;) ret[1 << i]= adj[i][i];
  return ret;
 }
 template <class T>  // O(V^3 2^V)
 inline sps<T> cactus_graph_num() const {
  auto ret= cycle_graph_num<T>();
  for (int i= V; i--;)
   for (int j= i; j--;) ret[(1 << i) | (1 << j)]+= adj[i][j];
  for (int i= V; i--;) ret[1 << i]= 0;
  return biconnect_to_connect(ret), loop_ignored_to_loop_permitted(ret), ret;
 }
 template <class T>  // O(V^3 2^V)
 inline sps<T> two_edge_connected_graph_num() const {
  const int sz2= sz / 2;
  sps<T> ret= connected_graph_num<T>(), tmp(sz2), tmp2;
  for (int i= V, I= sz2; --i; I>>= 1) {
   for (int t= 0; t < sz2; t+= I)
    for (int u= I, t2= t << 1; u--;) tmp[t | u]= ret[t2 | I | u];
   tmp2.assign(sz2, 0);
   for (int t= 0; t < sz2; t+= I)
    for (int j= i, J= I, t2= t << 1; J>>= 1, j--;)
     for (int s= J, J2= J * 2; s < I; s+= J2)
      for (int u= s + J; u-- > s;) tmp2[t | u]-= ret[t2 | u] * adj[i][j];
   tmp= SPS::convolve(tmp, SPS::exp(tmp2));
   for (int t= 0; t < sz2; t+= I)
    for (int u= I, t2= t << 1; u--;) ret[t2 | I | u]= tmp[t | u];
  }
  return ret;
 }
 template <class T>  // O(V^3 2^V)
 inline void transform_connect_by_bridge(sps<T> &f) const {
  const int sz2= sz / 2;
  sps<T> tmp(sz2), tmp2;
  for (int i= V, I= sz2; --i; I>>= 1) {
   for (int t= 0; t < sz2; t+= I)
    for (int u= I, t2= t << 1; u--;) tmp[t | u]= f[t2 | I | u];
   tmp2.assign(sz2, 0);
   for (int t= 0; t < sz2; t+= I)
    for (int j= i, J= I, t2= t << 1; J>>= 1, j--;)
     for (int s= J, J2= J * 2; s < I; s+= J2)
      for (int u= s + J; u-- > s;) tmp2[t | u]+= f[t2 | u] * adj[i][j];
   tmp= SPS::convolve(tmp, SPS::exp(tmp2));
   for (int t= 0; t < sz2; t+= I)
    for (int u= I, t2= t << 1; u--;) f[t2 | I | u]= tmp[t | u];
  }
 }
 template <class T>  // O(V^2 2^V)
 inline sps<T> acyclic_orientations() const {
  auto k= connected_component_num();
  sps<T> g(sz, 0);
  for (int s= sz; --s;)
   if (k[s] == __builtin_popcount(s)) g[s]= (k[s] + 1) & 1 ? -1 : 1;
  return SPS::template semi_relaxed_convolve<T>(g, 1);
 }
 template <class T>  // O(V^2 2^V)
 inline std::vector<T> colorings_using_exactly_k_colors_num() const {
  if (V == 0) return {0};  // impossible in any number of ways
  for (int i= V; i--;)
   if (adj[i][i]) return {0};  // impossible in any number of ways
  auto k= connected_component_num();
  std::vector<T> indep(sz, 0);
  for (int s= sz; --s;) indep[s]= k[s] == __builtin_popcount(s);
  return SPS::egf(indep);
 }
 template <class T>  // O(V^2 2^V)
 inline poly<T> chromatic_polynomial() const {
  auto e= colorings_using_exactly_k_colors_num<T>();
  if (e.back() == 0) return {0};
  poly<T> ret(V + 1, 0);
  T tmp[V]= {1};
  for (int i= 1, j; i < V; i++)
   for (j= i; j--; tmp[j]*= -i) ret[j + 1]+= tmp[j] * e[i], tmp[j + 1]+= tmp[j];
  for (int j= V; j--;) ret[j + 1]+= tmp[j];
  return ret;
 }
 template <class T>  //  O(V^2 2^V)
 inline T tutte_polynomial(T x, T y) const {
  int sum[sz], s, t, lim= 2, i, j;
  T fum[10'000]= {0, 1};
  std::vector<T> g= {0}, h;
  for (g.reserve(sz), h.reserve(sz), i= 0; i < V; i++) {
   for (sum[0]= j= 0; j < i; j++)
    for (s= t= 1 << j; s--;) sum[s | t]= sum[s] + adj[i][j];
   for (h.resize(s= 1 << i); s--; h[s]= g[s] * fum[sum[s]])
    for (; lim <= sum[s]; lim++) fum[lim]= fum[lim - 1] * y + 1;
   h= SPS::exp(h), std::copy(h.begin(), h.end(), std::back_inserter(g));
  }
  for (x-= 1, t= ~0, j= 0, i= V; i--;) j+= adj[i][i];
  for (bfs((s= sz) - 1, [&](int u) { t^= u; }); --s&= t;) g[s]*= x;
  return SPS::exp(g)[sz - 1] * pow(y, j);
 }
};
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 using GSPS= UndirectedGraphSetPowerSeries<15>;
 using SPS= SetPowerSeries<15>;
 int n, m;
 cin >> n >> m;
 GSPS g(n);
 for (int i= 0; i < m; ++i) {
  int u, v;
  cin >> u >> v, --u, --v;
  g.add_edge(u, v);
 }
 auto f= g.cycle_graph_num<long long>();
 for (int i= n; i--;) f[1 << i]= 1;
 g.transform_connect_by_bridge(f);
 f= SetPowerSeries<>::exp(f);
 cout << f.back() << '\n';
 return 0;
}

yukicoder

結果

テストケース

ソースコード