Set algorithm Part I

Sometimes we may meet with some functions $$$S\rightarrow V$$$(S is a set,V is a value),and we need to handle some transformations on it.

The article is for beginners whick is much easy, and I may continously update the article.

There are some features.

First the problem always give small $$$n$$$,such as $$$n\leq 15,n\leq20$$$.

Second,the time complexity is always $$$O(n2^n),O(3^n),O(n^22^n)$$$.

Let's do some assumption:

The values form a ring and they contain ring operations like addition,substraction,multification or division in constant time.

FWT/FMT

The most classical one is FWT/FMT.

Problem

Define $$$a(S),b(S)(S\subseteq U)$$$ on a set.

Get all $$$c(S)=\sum\limits_{i \oplus j=S}a_ib_j\qquad \oplus \text{is} \ \textrm{and,or,xor}$$$

The general idea:
Let $$$a, b, c$$$ be maps (functions) from a set $$$S$$$ to a value domain $$$V=(N/Q/C\cdots)$$$. We define a transformation $$$\text{FWT}$$$ (Fast Walsh Transform) as a map from the space of such functions to itself, i.e.,

$$$ \text{FWT}: (S \to V) \to (S \to V), $$$

with the following properties:

Invertibility: $$$\text{FWT}$$$ has an inverse map $$$\text{FWT}^{-1}$$$.
Efficiency: $$$\text{FWT}$$$ can be computed in $$$O(n \log n)$$$ time.
Pointwise product property: For all $$$i \in S$$$,

$$$ \text{FWT}(a)_i \cdot \text{FWT}(b)_i = \text{FWT}(c)_i, $$$

Calculating $$$\mathrm{FWT(a),FWT(b)}$$$,then pointwise product between them and do the $$$\mathrm{FWT}^{-1}$$$,it's $$$c$$$.

I like cpp,so I use | for $$$\textrm{or}$$$,& for $$$\textrm{and}$$$,^ for $$$\textrm{xor}$$$.

OR FMT

a.k.a Zeta Transform,SOS DP,Yate's DP,Mobius Transform

$$$FWT(a)(i)=\sum_{(i|j)=i}a(i)$$$

The calculation is like this.

for(int o=1;o*2<=n;o<<=1)
    for(int i=0;i<n;i+=o<<1)
        for(int j=0;j<o;++j)
            a[i+j+o]=a[i+j+o]+a[i+j];

We first split the $$$a$$$ correspond to the current bit to $$$a_0,a_1$$$.Assume we are process the x-th bit,in the $$$a_k$$$ the x-th bit is $$$k$$$.We do a divide and conquer.Then

$$$FWT_0=a_0\\FWT_1=a_0+a_1$$$

We difine the addition on $$$(S\rightarrow V)$$$ is addition on each on single element.

And its invertion transform is easy to find.

$$$\mathrm{FWT}^{-1}_0=a_0\\\mathrm{FWT}^{-1}_1=a_1-a_0$$$

$$$\textrm{FWT}^{-1}$$$ a.k.a inverse Mobius Transform.

And verify the Pointwise product property.

$$$ \begin{align*} \mathrm{FWT}(a)(i) \cdot \mathrm{FWT}(b)(i) &= \sum_{\substack{(i|j)=i}} a(j) \sum_{\substack{(i|k)=i}} b(k) \\ &= \sum_{\substack{(i|(j|k))=i}} a(j) b(k) \\ &= \sum_{\substack{(i|x)=i}} c(x) \\ &= \mathrm{FWT}(c)(i) \end{align*} $$$

Afterwards,I will omit some details.

AND FMT

$$$\mathrm{FWT}(a)(i)=\sum_{(i\&j)=i}a(i)$$$

for(int o=1;o*2<=n;o<<=1)
    for(int i=0;i<n;i+=o<<1)
        for(int j=0;j<o;++j)
            a[i+j]=a[i+j]+a[i+j+o];

$$$FWT_0=a_0+a_1\\FWT_1=a_1$$$ $$$\mathrm{FWT}^{-1}_0=a_0-a_1\\\mathrm{FWT}^{-1}_1=a_1$$$ $$$ \begin{align*} \mathrm{FWT}(a)(i) \cdot \mathrm{FWT}(b)(i) &=\sum_{(i\&j)=i}a(j)\sum_{(i\&k)=i}b(k)\\ &=\sum_{(i\&(j\&k))=i}a(j)b(k)\\ &=\sum_{(i\&x)=i}c(x)\\ &=\mathrm{FWT}(c)(i)\\ \end{align*} $$$

It's the same as OR,because we can flip all the bits at the beginning and flip them back at the end.

XOR FWT

define $$$W(x,i)=popcount(x\wedge i)\bmod 2$$$

which satisfy $$$W(x,i\wedge j)=W(x,i)\wedge W(x,j)$$$

$$$\mathrm{FWT}(a)_i=\sum_j a(j)(-1)^{W(i,j)}$$$

for(int o=1;o*2<=n;o<<=1)
    for(int i=0;i<n;i+=o<<1)
        for(int j=0;j<o;++j){
            ll x=f[i+j],y=f[i+j+o];
            f[i+j]=(x+y);
            f[i+j+o]=(x-y);
        }

$$$FWT_0=a_0+a_1\\FWT_1=a_0-a_1$$$ $$$ \mathrm{FWT}^{-1}_0=\frac{a_0+a_1}{2}\\ \mathrm{FWT}^{-1}_1=\frac{a_0-a_1}{2}\\ $$$ $$$ \begin{align*} \mathrm{FWT}(a)_i \cdot \mathrm{FWT}(b)_i &=\sum_{j}a(j)(-1)^{W(i,j)}\sum_{k}b(k)(-1)^{W(i,k)}\\ &=\sum_{j,k}a(j)b(k)(-1)^{W(i,j)\wedge W(i,k)}\\ &=\sum_{j,k}a(j)b(k)(-1)^{W(i,j\wedge k)}\\ &=\sum_{x}c(x)(-1)^{W(i,x)}\\ &=\mathrm{FWT}(c)_i\\ \end{align*} $$$

Subset Sum Convolution

Problem

Define $$$a(S),b(S)(S\subseteq U)$$$ on a set.

Get all $$$c(S)=\sum\limits_{i\subseteq S}a(i)b(S\setminus i)$$$

The general idea by Intuition:

for $$$S$$$,calculate sum $$$a_ib_j$$$ of for all $$$i,j(|i|+|j|=S)$$$.

and only if $$$|i\cap j|=|S|$$$, it's valid. So do apply inclusion-exclusion principle on it,we can get the result.

Ranked Mobius Transform and inversion

define

$$$\hat{f}(x,S)=\sum\limits_{\substack{i\subseteq S\\|i|=x}}f(i)$$$

the inverse

$$$f(S)=\hat{f}(|S|,S)$$$

Fast Subset Convolution

define

$$$d(x,S)=\sum_i \hat{a}(x,S)\hat{b}(x-i,S)$$$

one can show that

$$$c(S)=\sum_{i\subseteq S}(-1)^{|S|-|i|}d(|S|,i)$$$

for(int mask = 0; mask < (1 << n); mask++) {
    fa[__builtin_popcount(mask)][mask] = a[mask];
    fb[__builtin_popcount(mask)][mask] = b[mask];
}
for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        for(int mask = 0; mask < (1 << n); mask++) {
            if((mask & (1 << j)) != 0) {
                fa[i][mask] += fa[i][mask ^ (1 << j)];
                fb[i][mask] += fb[i][mask ^ (1 << j)];
            }
        }
    }
}
for(int mask = 0; mask < (1 << n); mask++) {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= i; j++) {
            d[i][mask] += fa[j][mask] * fb[i - j][mask];
        } 
    }
}
for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        for(int mask = 0; mask < (1 << n); mask++) {
            if((mask & (1 << j)) != 0) {
                h[i][mask] -= h[i][mask ^ (1 << j)];
            }
        }
    }
}
for(int mask = 0; mask < (1 << n); mask++)  c[mask] = h[__builtin_popcount(mask)][mask];

In the $$$\sum_{i\subseteq S}(-1)^{|S|-|i|}\sum_j \hat{a}(x,i)\hat{b}(|i|-x,i)$$$. for exact $$$S$$$, a pair of $$$U,V$$$ in $$$\hat{a},\hat{b}$$$ is calculated for

$$$ \begin{cases} \sum_{i=|U\cup V|}^{|S|}\binom{|S|-|U\cup V|}{i}(-1)^{|S|-|U\cup V|-i}=0 & \text{if } |U\cup V| \lt |S| \\ 1 & \text{if } |U\cup V|=|S| \lt 0 \end{cases} $$$

times.

So it's right.

Online Convolution (Luogu4221)

Let begin with the problem. P4221 [WC2018] 州区划分 — 洛谷

We can quickly solve the problem by DP.

The transitions are like $$$f(S)=\sum_{T\sub S} f(T)g(S-T)$$$,where $$$g$$$ is fixed.

The new transition need the previous transition, so how to transition quickly enough?

Add a dimension $$$i=|S|$$$,and use the subset convolution online. We can solve the problem.

Exercise

CF1713F

reorder $$$a_i=a_{n-i}$$$

get the diagnal c_i.

$$$a\rightarrow c \rightarrow b$$$ is a series of transforms ,so just do the inverse.

and calculate the contribution

code

QOJ13083

$$$ \begin{align*} ans&=\sum_{P,Q}[f(P)=f(Q)][P\cap Q=\varnothing]\prod_{i\in P\cup Q}a_i\\ \end{align*} $$$

We see if $$$f(P)$$$ is certain,the mask of $$$P$$$ is easier to describe.

$$$ \begin{align*} [f(P)=f(Q)]&=\prod_i[f(P)_i=f(Q)_i]\\ &=\prod_if(P)_i\land f(Q)_i\lor \lnot f(P)_i\land \lnot f(Q)_i \\ &=\prod_i2f(P)_i\land f(Q)_i-f(P)_i-f(Q)_i+1\\ &=\sum_{S\subseteq f(P),T\subseteq f(Q)}2^{|S\cap T|}(-1)^{|S|+|T|}\\ \end{align*} $$$

now the $$$f(P),f(Q)$$$ is limited by $$$S,T$$$,so enumerate $$$S,T$$$.

$$$ \begin{align*} ans&=\sum_{P,Q}[f(P)=f(Q)][P\cap Q=\varnothing]\prod_{i\in P\cup Q}a_i\\ &=\sum_{P,Q}\sum_{S\subseteq f(P),T\subseteq f(Q)}2^{|S\cap T|}(-1)^{|S|+|T|}[P\cap Q=\varnothing]\prod_{i\in P\cup Q}a_i\\ &=\sum_{S,T}2^{|S\cap T|}(-1)^{|S|+|T|}\sum_{S\subseteq f(P),T\subseteq f(Q)}[P\cap Q=\varnothing]\prod_{i\in P\cup Q}a_i\\ \end{align*} $$$ $$$V(S)=\{X|S\subseteq X\}$$$ $$$ \begin{align*} ans &=\sum_{S,T}2^{|S\cap T|}(-1)^{|S|+|T|}\sum_{i\in (V(S)\cup V(T))\setminus(V(S)\cap V(T))}(a_i+1)\sum_{i\in V(S)\cap V(T)}(2a_i+1)\\ \end{align*} $$$ $$$f(i)=\prod_{i\subseteq j}a_j+1$$$ $$$g(i)=\prod_{i\subseteq j}2a_j+1$$$ $$$ \begin{align*} ans &=\sum_{S,T}2^{|S\cap T|}(-1)^{|S|+|T|}g(S\cup T)\frac{f(S)f(T)}{f^2(S\cup T)}\\ &=\sum_{S,T}g(S\cup T)\frac{(-2)^{|S|}f(S)(-2)^{|T|}f(T)}{f^2(S\cup T)2^{|S\cup T|}}\\ \end{align*} $$$ $$$\hat{f}(S)=(-2)^{|S|}f(S)(-2)$$$ $$$\hat{g}(S)=\frac{g(S)}{f^2(S)2^{|S|}}$$$

Do the FWT convolution (OR) $$$\hat{f}\times \hat{f}$$$

$$$ \begin{align*} ans&=\sum_{S}(\hat{f}\times \hat{f})(S)g(S)\\ \end{align*} $$$

and handle some details.

code

Counting on the graph

Counting Tree Subgraph (No problem,compared with Matrix-Tree)

Given a simple undirected graph, count how many subgraph of it is a tree.

Obviously, we can use Matrix-Tree Theorem to solve it.

Input:

$$$ n\ m\\ u_1 \ v_1\\ u_2 \ v_2\\ \vdots\\ u_m \ v_m\\ $$$

$$$n$$$ is number of vertixs, $$$m$$$ is the number of edges,and note the points are 1-indexed,output the $$$ans \bmod 992844353$$$.

The Matrix-Tree One

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;

ll mod_pow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

ll mod_inv(ll a) {
    return mod_pow(a, MOD - 2);
}

ll det_mod(vector<vector<ll>> &mat, int n) {
    ll res = 1;
    for (int i = 0; i < n; i++) {
        int p = -1;
        for (int j = i; j < n; j++) {
            if (mat[j][i]) {
                p = j;
                break;
            }
        }
        if (p == -1) return 0;
        if (p != i) {
            swap(mat[i], mat[p]);
            res = (MOD - res) % MOD;
        }
        res = res * mat[i][i] % MOD;
        ll inv = mod_inv(mat[i][i]);
        for (int j = i; j < n; j++)
            mat[i][j] = mat[i][j] * inv % MOD;
        for (int j = i + 1; j < n; j++) {
            if (!mat[j][i]) continue;
            ll f = mat[j][i];
            for (int k = i; k < n; k++)
                mat[j][k] = (mat[j][k] - f * mat[i][k] % MOD + MOD) % MOD;
        }
    }
    return res;
}

ll countST(int n, const vector<pair<int, int>> &e) {
    if (n <= 1) return 1;
    vector<vector<ll>> L(n, vector<ll>(n, 0));
    vector<int> deg(n, 0);
    for (auto [u, v] : e) {
        u--, v--;
        deg[u]++, deg[v]++;
    }
    for (int i = 0; i < n; i++)
        L[i][i] = deg[i] % MOD;
    for (auto [u, v] : e) {
        u--, v--;
        L[u][v] = (L[u][v] - 1 + MOD) % MOD;
        L[v][u] = (L[v][u] - 1 + MOD) % MOD;
    }
    vector<vector<ll>> sub(n - 1, vector<ll>(n - 1, 0));
    for (int i = 1; i < n; i++)
        for (int j = 1; j < n; j++)
            sub[i - 1][j - 1] = L[i][j];
    return det_mod(sub, n - 1);
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> e(m);
    for (int i = 0; i < m; i++)
        cin >> e[i].first >> e[i].second;
    cout << countST(n, e) << endl;
    return 0;
}
//Generated by Deepseek

How can we do it manually?

It makes sense to set a root to better transition.

$$$dp[i][S]$$$ means the number of trees rooted at $$$i$$$ in the subgraph $$$S$$$ .

Enumerate $$$T\sub S$$$ with the lowest bit in $$$S\oplus 2^{i}$$$as a subtree from $$$i$$$ and make transition.

#include<bits/stdc++.h>
using namespace std;

int n,m;
int e[20][20];
typedef long long ll;
ll f[20][(1<<20)+123];
const int P=998244353;
void madd(ll &x,ll y){x=(x+y)%P;}
int main(){
    cin>>n>>m;
    for(int i=1,u,v;i<=m;++i){
        cin>>u>>v;
        e[u-1][v-1]=e[v-1][u-1]=1;
    }
    for(int i=0;i<n;++i)f[i][1<<i]=1;
    for(int mask=0;mask<1<<n;++mask)
        for(int i=0;i<n;++i)if(mask>>i&1){
            int smask=mask^(1<<i);
            int lb=smask&(-smask);
            for(int j=smask;j;j=(j-1)&smask){
                if(!(j&lb))continue;
                for(int k=0;k<n;++k)if((j>>k&1)&&e[i][k]){
                    madd(f[i][mask],f[k][j]*f[i][mask^j]);
                }
            }
        }
    printf("%lld\n",f[0][(1<<n)-1]);
    return 0;
}

Observing that a tree can be rooted anywhere , we can only use $$$dp[S]$$$.

#include<bits/stdc++.h>
using namespace std;

int n,m;
int e[20][20];
typedef long long ll;
ll f[(1<<20)+123];
const int P=998244353;
void madd(ll &x,ll y){x=(x+y)%P;}
ll inv[21];
int main(){
    inv[1]=1;for(int i=2;i<=20;++i)inv[i]=P-inv[P%i]*(P/i)%P;
    cin>>n>>m;
    for(int i=1,u,v;i<=m;++i){
        cin>>u>>v;
        e[u-1][v-1]=e[v-1][u-1]=1;
    }
    for(int i=0;i<n;++i)f[1<<i]=1;
    for(int mask=0;mask<1<<n;++mask)
        for(int i=0;i<n;++i)if(mask>>i&1){
            int smask=mask^(1<<i);
            int lb=smask&(-smask);
            for(int j=smask;j;j=(j-1)&smask){
                if(!(j&lb))continue;
                for(int k=0;k<n;++k)if((j>>k&1)&&e[i][k]){
                    madd(f[mask],f[j]*f[mask^j]%P*inv[__builtin_popcount(j)]%P*inv[__builtin_popcount(mask^j)]);
                }
            }
        }
    printf("%lld\n",f[(1<<n)-1]*inv[n]%P);
    return 0;
}

Time complexity: $$$O(n^23^n)$$$.

Space complexity: $$$O(n2^n)$$$ or $$$O(2^n)$$$.

Counting Cactus (QOJ7412)

It becomes more tricky.

$$$f[i][S]$$$ means $$$i$$$ is the root, $$$i$$$ is connect to only one vertex or only in one cycle, the subtree is state $$$S$$$.

$$$g[i][j]$$$ means there is a path from $$$i$$$ to $$$j$$$ ,the subtree is state $$$S$$$.

$$$h[i][j]$$$ means $$$i$$$ is the root, the subtree is state $$$S$$$.

Transition:

$$$f\leftarrow h$$$ , a root connected to a tree
$$$f\leftarrow g$$$ a cycle is closed.
$$$g\leftarrow h$$$ extend the chain
$$$h\leftarrow f$$$ add cycles or subtrees to the root.

The final ans is $$$h[x][S]$$$.

Overall time complexity $$$O(n^23^n)$$$.

It's not good to delete the root dimension.

code

Counting SCC (Luogu P11714)

Consider PIE, calculate the number of DAG of scc which size is larger than $$$2$$$.

If there is $$$cnt$$$ scc which has $$$0$$$ in-degree, give it $$$(-1)^{cnt}$$$ coef.

$$$dp[S]$$$ means the subproblem for subgraph $$$S$$$.

Handle some transition and it's done.

code

Set algorithm Part II

The first part has talked about some algorithm and its basic practice. But they are not organized. SPS solves it.

The topic: Set power series.

We have former power series (i.e. generating function) to describe a integer sequence. But if we want to handle the map from a set to a value, we need set power series.

It's not something new, just to wrap all the things above up.

Note

Single uppercase letter means a set.

Single lowercase letter means a power series.

$$$x$$$ is the variable.

The global set $$$U={1,2,\cdots,n}$$$.

$$$2^X={Y|Y\subseteq X}$$$

Definition

Set power series is a function $$$f: 2^U \rightarrow F$$$ where F is a field ($$$C,R,Q$$$).

Addition

$$$f,g$$$ are power series , $$$h=f+g$$$, then $$$h_i=f_i+g_i$$$.

Subtraction

$$$f,g$$$ are power series , $$$h=f-g$$$, then $$$h_i=f_i-g_i$$$.

We note $$$cx^S$$$ as a power series where $$$f_S=c$$$ and other coefficents are zero.

$$$f=\sum_S f_Sx^S$$$

Multiplication

Take a binary operation $$$\ast$$$ that satisfy $$$X\ast Y=Y\ast X,(X\ast Y)\ast Z=X\ast (Y\ast Z),X\ast \varnothing=X$$$.

Define $$$h=f\ast g$$$, $$$h=\sum_S h_S x^S=\sum_X\sum_Yf_Xg_Y x^{X\ast Y}$$$.

We have $$$f\ast g=f\ast g,(f\ast g)\ast h=f\ast (g\ast h),f\ast \varnothing=f$$$.

Convolution

Set Union/Intersection Convolution

The multiplication is identical to the FWT.

Take $$$X\ast Y=X\cup Y$$$ or $$$X\ast Y=X\cap Y$$$.

We use $$$\cup$$$ below.

D&C Multiplication

write $$$f=f^-+x^{{n}}f^+,g=g^-+x^{{n}}g^+$$$.

$f\ast g=(f^-+x^{{n}}f^+)\ast(g^-+x^{{n}}g^+)\ =f^-g^-+x^{{n}}((f^+f^-)\ast(g^-+g^+)-f^-g^-)$.

$$$T(n)=T(n/2)+2^n=O(n2^n)$$$.

FMT

mentioned above ,they are the same.

It's called 'Mobius Transform'.

Set Symmetric Difference Convolution

The multiplication is identical to the FWT, too.

Take $$$X\ast Y=X\oplus Y$$$.

D&C Multiplication

write $$$f=f^-+x^{{n}}f^+,g=g^-+x^{{n}}g^+$$$.

$f\ast g=(f^-+x^{{n}}f^+)\ast(g^-+x^{{n}}g^+)\ =f^-g^-+f^+g^++x^{{n}}(f^-g^++f^+g^-)$.

$$$T(n)=T(n/2)+2^n=O(n2^n)$$$.

FWT

It's called 'Walsh Transform'.

Subset Convolution

$X\ast Y=\begin{cases} X\cup Y & X\cap Y = \varnothing\ \varnothing & X\cap Y \neq \varnothing \end{cases}$

It's the same as Subset Convolution.

Composition

Source:

https://www.luogu.com.cn/problem/P12230 https://www.luogu.com.cn/problem/P12231

They are all special cases of composition.

$$$h$$$ is a polynomial, $$$f$$$ is a set power series.

We use subset operation below.

$$$h(f)=\sum_i h_i f^i$$$

If $$$f_0=0$$$,then $$$i \gt n$$$ is useless.

We need solve FMT to get $$$f^i$$$ ,and do the multiplication and addition. Finally we do IFMT to get the answer.

$$$exp(f)=\sum_{i=0}^{\infty}\frac{x^i}{i!}$$$ $$$ln(1+f)=\sum_{i=1}^{\infty}\frac{(-1)^{i+1}x^i}{i}$$$

But it's different when it comes into 'inverse'.

Source: https://www.luogu.com.cn/problem/P12232

$$$f\ast g=x^{\varnothing}$$$, $$$f$$$ is given ,solve for $$$g$$$.

Use the classic 'subset mind': first do FMT, then for each $$$S$$$ treat it as a polynomial and get its inverse.

Three formula:

If $$$f\cdot g = 1$$$,then $$$g_n=-\frac{1}{f_0}\sum_{i=1}^{n}f_ig_{n-i}$$$.

If $$$g=exp(f)$$$,then $$$g_n=\frac{1}{n}\sum_{i=1}^{n}f_iig_{n-i}$$$.

If $$$g=ln(f)$$$,then $$$g_n=f_n-\frac{1}{n}\sum_{i=0}^{n-1}g_iif_{n-i}$$$.

Example

Problem 1

There is a machine. Every time Alice push the button, the machine give $$$S$$$ in probability $$$p_S$$$. Alice initially have no sets and she keeps pushing the button until the union is $$$U$$$.Ask the exceptation of the number of pushing the button.

$$$n\leq 20$$$

$$$ans=[x^U]\sum k(p^k-p^{k-1})$$$.

Do mobius transform and reverse it and we are done.

$$$O(n2^n)$$$.

Problem 2: Topcoder SRM 518 Nim

Alice and Bob are playing Nim. $$$m$$$ piles of stones. Ask the number of stones where each number is a prime $$$\leq l$$$.

$$$m\leq 10^9,l\leq 10^5$$$.

$$$ans=\sum_{S\neq \varnothing}(\sum_T [T \text{ is prime}])^m$$$

Do walsh transform and inverse. $$$O(l(\log m+\log l))$$$.

Problem 3: Connected subgraph counting

Count connected subgraph of a graph of $$$n$$$ vertices and $$$m$$$ edges.

$$$n\leq 20,m\leq n(n-1)/2$$$.

Let $$$g_S$$$ be the number of subgraph of $$$S$$$, $$$f_S$$$ be the number of connected subgraph of $$$S$$$.

$$$1+g_S=\sum \frac{f^k}{k!}=\exp(f)$$$

$$$f=\ln(1+g)$$$

$$$O(n^22^n)$$$.

Template

template<const ll mod>
struct SPS{
int n;
vector<ll> coef;
void resize(int n_,int v=0){
    n=n_;
    coef.resize(1<<n,v);
}
SPS(){}
SPS(int n_){resize(n_,0);}
SPS(vector<ll> a):coef(a){}
ll qpow(ll a,ll b,ll p){
    ll c=1;for(;b;b>>=1,a=a*a%p)if(b&1)c=c*a%p;return c;
}
ll inv(ll x){
    return qpow(x,mod-2,mod);
}
ll& operator [](size_t x){
    return coef[x];
}
template<class Op>
void rec(vector<ll> &a,int n,Op op,int p=0){
    if(n<=6){
        for(int o=1;o<1<<n;o<<=1)
            for(int i=0;i<1<<n;i+=o<<1)
                for(int j=0;j<o;++j)
                    op(coef[p+i+j],coef[p+i+j+o]);
    }else{
        rec(a,n-1,op,p);
        rec(a,n-1,op,p+(1<<n-1));
        for(int i=0;i<1<<n-1;++i)op(a[p+i],a[p+i+(1<<n-1)]);
    }
}
void OR(){
    rec(coef,n,[&](ll &x,ll &y){y+=x;if(y>=mod)y-=mod;});
}
void IOR(){
    rec(coef,n,[&](ll &x,ll &y){y+=mod-x;if(y>=mod)y-=mod;});
}
void AND(){
    rec(coef,n,[&](ll &x,ll &y){x+=y;if(x>=mod)x-=mod;});
}
void IAND(){
    rec(coef,n,[&](ll &x,ll &y){x+=mod-y;if(x>=mod)x-=mod;});
}
void XOR(){
    rec(coef,n,[&](ll &x,ll &y){
        ll tx=x,ty=y;x=tx+ty,y=tx+mod-ty;if(x>=mod)x-=mod;if(y>=mod)y-=mod;
    });
}
void IXOR(){
    rec(coef,n,[&](ll &x,ll &y){
        ll tx=x,ty=y;x=tx+ty,y=tx+mod-ty;if(x>=mod)x-=mod;if(y>=mod)y-=mod;
    });
    ll tmp=1;for(int i=0;i<n;++i)tmp=tmp*(mod+1>>1)%mod;
    for(int i=0;i<1<<n;++i)coef[i]=coef[i]*tmp%mod;
}
SPS operator * (const SPS B){
    SPS res(n);
    for(int i=0;i<1<<n;++i)res.coef[i]=coef[i]*B.coef[i]%mod;
    return res;
}
SPS operator & (SPS B){
    SPS A(n);
    for(int i=0;i<1<<n;++i)A.coef[i]=coef[i];
    A.AND(),B.AND();
    A=A*B;
    A.IAND();
    return A;
}
SPS operator | (SPS B){
    SPS A(n);
    for(int i=0;i<1<<n;++i)A.coef[i]=coef[i];
    A.OR(),B.OR();
    A=A*B;
    A.IOR();
    return A;
}
SPS operator ^ (SPS B){
    SPS A(n);
    for(int i=0;i<1<<n;++i)A.coef[i]=coef[i];
    A.XOR(),B.XOR();
    A=A*B;
    A.IXOR();
    return A;
}
//subset convolution
SPS operator || (SPS B){
    vector<SPS> f(n+1,SPS(n)),g(n+1,SPS(n)),h(n+1,SPS(n));
    for(int i=0;i<1<<n;++i){
        f[__builtin_popcount(i)].coef[i]=coef[i];
        g[__builtin_popcount(i)].coef[i]=B.coef[i];
    }
    for(int i=0;i<=n;++i)f[i].OR(),g[i].OR();
    for(int i=0;i<=n;++i)
        for(int j=0;j<=i;++j)
            for(int k=0;k<1<<n;++k)
                h[i].coef[k]=(h[i].coef[k]+f[j].coef[k]*g[i-j].coef[k])%mod;
    for(int i=0;i<=n;++i)h[i].IOR();
    SPS res(n);
    for(int i=0;i<1<<n;++i)res.coef[i]=h[__builtin_popcount(i)].coef[i];
    return res;
}
SPS exp(){
    vector<ll> inv(n+1);
    inv[1]=1;for(int i=2;i<=n;++i)inv[i]=mod-inv[mod%i]*(mod/i)%mod;
    SPS res(n);
    vector<SPS> f(n+1,SPS(n)),g(n+1,SPS(n));
    for(int i=0;i<1<<n;++i)f[__builtin_popcount(i)][i]=coef[i];
    for(int i=0;i<=n;++i)f[i].OR();
    for(int i=0;i<1<<n;++i){
        g[0][i]=1;
        for(int j=1;j<=n;++j){
            for(int k=1;k<=j;++k){
                g[j][i]=(g[j][i]+f[k][i]*k%mod*g[j-k][i])%mod;
            }
            g[j][i]=g[j][i]*inv[j]%mod;
        }
    }
    for(int i=0;i<=n;++i)g[i].IOR();
    for(int i=0;i<1<<n;++i)res.coef[i]=g[__builtin_popcount(i)][i];
    return res;
}
SPS ln(){
    vector<ll> inv(n+1);
    inv[1]=1;for(int i=2;i<=n;++i)inv[i]=mod-inv[mod%i]*(mod/i)%mod;
    SPS res(n);
    vector<SPS> f(n+1,SPS(n)),g(n+1,SPS(n));
    for(int i=0;i<1<<n;++i)f[__builtin_popcount(i)][i]=coef[i];
    for(int i=0;i<=n;++i)f[i].OR();
    for(int i=0;i<1<<n;++i){
        g[0][i]=0;
        for(int j=1;j<=n;++j){
            for(int k=1;k<=j-1;++k){
                g[j][i]=(g[j][i]+g[k][i]*k%mod*f[j-k][i])%mod;
            }
            g[j][i]=(f[j][i]+mod-g[j][i]*inv[j]%mod)%mod;
        }
    }
    for(int i=0;i<=n;++i)g[i].IOR();
    for(int i=0;i<1<<n;++i)res.coef[i]=g[__builtin_popcount(i)][i];
    return res;
}
SPS Inv(){
    SPS res(n);
    vector<SPS> f(n+1,SPS(n)),g(n+1,SPS(n));
    for(int i=0;i<1<<n;++i)f[__builtin_popcount(i)][i]=coef[i];
    for(int i=0;i<=n;++i)f[i].OR();
    g[0][0]=inv(coef[0]);
    for(int i=0;i<1<<n;++i){
        g[0][i]=g[0][0];
        for(int j=1;j<=n;++j){
            g[j][i]=0;
            for(int k=1;k<=j;++k){
                g[j][i]=(g[j][i]+mod-f[k][i]*g[j-k][i]%mod)%mod;
            }
            g[j][i]=g[j][i]*g[0][0]%mod;
        }
    }
    for(int i=0;i<=n;++i)g[i].IOR();
    for(int i=0;i<1<<n;++i)res.coef[i]=g[__builtin_popcount(i)][i];
    return res;
}
};
typedef SPS<998244353> SPS998;