Given an undirected graph (G=(V,E)) with (|V|=n \leq 16) and (|E| \leq \binom{n}{2}), compute the sum of weights of all unicyclic subgraphs. The weight of a unicyclic subgraph is defined as (2^w), where (w) is the number of non-leaf nodes in the subgraph.

We first calculate cycle_count[S], the number of simple cycles spanning subset (S \subseteq V), using a minimal-element bitmask DP technique. Fix the smallest node in (S) as the cycle's starting point to avoid overcounting cycles in both directions. After computing DP results, divide by 2 to correct for bidirectional traversals, and set cycle_count[S] = 0 for subsets with size ≤2 since these do not form valid cycles. This runs in (O(2^n n^2)) time.

To compute the number of unicyclic subgraphs on subset (S) (denoted unicyclic_count[S]), a naive approach enumerates all subsets (T \subset S) (the cycle cmoponent), contracts (T) into a single node, and applies Kirchhoff’s theorem to count spanning trees on the remaining structure. This gives an (O(3^n n^3)) solution, which scores approximately 30% of the points.

To incorporate the weight (2^w), we use an inclusion-exclusion strategy focused on leaf nodes. The total weight can be expressed as: [ \text{total} = \sum_{S \subseteq V} \sum_{T \subseteq S} \text{unicyclic_count}[S \setminus T] \cdot 2^{|S \setminus T|} \cdot (-1)^{|T|} \cdot \prod_{x \in T} \text{deg}{S \setminus T}(x) ] where (\text{deg}{S \setminus T}(x)) is the number of edges between (x) and nodes in (S \setminus T). Reorganizing terms gives: [ \text{total} = \sum_{P \subseteq V} \text{unicyclic_count}[P] \cdot 2^{|P|} \cdot \prod_{x \notin P} \left(1 - \text{deg}_P(x)\right) ] allowing computation in (O(2^n n)) time once unicyclic_count is known.

Method 1: Leaf Inclusion-Exclusion for Unicyclic Count

We compute unicyclic_count[S] using the recurrence: [ \text{unicyclic_count}[S] = \text{cycle_count}[S] - \sum_{\emptyset \neq T \subset S} \left( \prod_{x \in T} \text{deg}_{S \setminus T}(x) \right) \cdot \text{unicyclic_count}[S \setminus T] \cdot (-1)^{|T|} ] This runs in (O(3^n)) time. We precompute product terms efficiently using subset enumeration.

#include <cstdio>
#include <vector>
using namespace std;

const int MOD = 998244353;
typedef long long ll;

int dp_path[1<<16][16];
int cycle_count[1<<16];
int adj_mask[16];
int n, m, full_mask;
int pow2[17];
int res;

int read() {
    char c = getchar();
    int x = 0;
    while(c < '0' || c > '9') c = getchar();
    do {
        x = (x << 1) + (x << 3) + (c - '0');
        c = getchar();
    } while(c >= '0' && c <= '9');
    return x;
}

void add(int &x, int v) { if((x += v) >= MOD) x -= MOD; }
void sub(int &x, int v) { if((x -= v) < 0) x += MOD; }

int main() {
    n = read(); m = read();
    full_mask = (1 << n) - 1;
    for(int i=0; i<m; ++i) {
        int u = read()-1, v = read()-1;
        adj_mask[u] |= (1 << v);
        adj_mask[v] |= (1 << u);
    }

    for(int i=0; i<n; ++i) dp_path[1<<i][i] = 1;
    pow2[0] = 1;
    for(int i=1; i<=n; ++i) add(pow2[i] = pow2[i-1], pow2[i-1]);

    // Compute paths from minimal node to all nodes in subset s
    for(int s=1; s < (1<<n); ++s) {
        int min_node = __builtin_ctz(s);
        for(int u=min_node; u<n; ++u) {
            if(!dp_path[s][u]) continue;
            for(int v=min_node+1; v<n; ++v) {
                if(s & (1<<v)) continue;
                if(adj_mask[u] & (1<<v)) add(dp_path[s | (1<<v)][v], dp_path[s][u]);
            }
        }
    }

    // Calculate cycle counts
    for(int s=1; s < (1<<n); ++s) {
        int min_node = __builtin_ctz(s);
        for(int u=min_node+1; u<n; ++u) {
            if(adj_mask[u] & (1<<min_node)) add(cycle_count[s], dp_path[s][u]);
        }
        // Divide by 2 to correct bidirectional cycles
        if(cycle_count[s] % 2) cycle_count[s] += MOD;
        cycle_count[s] >>= 1;
        // Exclude invalid small subsets
        if(__builtin_popcount(s) <= 2) cycle_count[s] = 0;
    }

    vector<int> product_cache(1<<n, 0);
    vector<int> stack;
    res = 0;

    // Compute final result via inclusion-exclusion
    for(int s=0; s < (1<<n); ++s) {
        if(!cycle_count[s]) continue;
        int current = (ll)pow2[__builtin_popcount(s)] * cycle_count[s] % MOD;
        vector<int> deg(n);
        for(int u=0; u<n; ++u) {
            if(!(s & (1<<u))) {
                deg[u] = __builtin_popcount(adj_mask[u] & s);
                current = (ll)current * (MOD + 1 - deg[u]) % MOD;
            }
        }
        add(res, current);

        // Update cycle counts for supersets
        int complement = full_mask ^ s;
        stack.clear();
        for(int d=complement; d; d=(d-1)&complement) stack.push_back(d);
        product_cache[0] = 1;
        while(!stack.empty()) {
            int d = stack.back(); stack.pop_back();
            int lsb = __builtin_ctz(d);
            product_cache[d] = (ll)product_cache[d ^ (1<<lsb)] * deg[lsb] % MOD;
            if(__builtin_parity(d)) add(cycle_count[s | d], (ll)cycle_count[s] * product_cache[d] % MOD);
            else sub(cycle_count[s | d], (ll)cycle_count[s] * product_cache[d] % MOD);
        }
    }

    printf("%d\n", res);
    return 0;
}

Method 2: Graph Orientation Technique

We model unicyclic subgraphs as directed graphs where each node has exactly one outgoing edge (forming an inward unicyclic forest). Using set power series and logarithmic transforms, we extract connected components, then subtract invalid 2-node cycle contributions using Kirchhoff’s theorem.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MOD = 998244353;
typedef long long ll;

int dp_path[1<<16][16];
int cycle_count[1<<16];
int adj_mask[16];
int n, m, full_mask;
int pow2[17], inv[17];
int gen_func[17][1<<16], ln_func[17][1<<16];
int mat[17][17], mat_size;
int res;

int read() {
    char c = getchar();
    int x = 0;
    while(c < '0' || c > '9') c = getchar();
    do {
        x = (x << 1) + (x << 3) + (c - '0');
        c = getchar();
    } while(c >= '0' && c <= '9');
    return x;
}

void add(int &x, int v) { if((x += v) >= MOD) x -= MOD; }
void sub(int &x, int v) { if((x -= v) < 0) x += MOD; }

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

int determinant() {
    bool swapped = false;
    int det_val = 1;
    for(int i=1; i<=mat_size; ++i) {
        int pivot = i;
        while(pivot <= mat_size && !mat[pivot][i]) pivot++;
        if(pivot > mat_size) return 0;
        if(pivot != i) {
            swap(mat[pivot], mat[i]);
            swapped ^= 1;
        }
        det_val = (ll)det_val * mat[i][i] % MOD;
        int inv_pivot = qpow(mat[i][i]);
        for(int j=i; j<=mat_size; ++j) mat[i][j] = (ll)mat[i][j] * inv_pivot % MOD;
        for(int j=i+1; j<=mat_size; ++j) {
            for(int k=mat_size; k>=i; --k) {
                sub(mat[j][k], (ll)mat[j][i] * mat[i][k] % MOD);
            }
        }
    }
    return swapped ? (MOD - det_val) % MOD : det_val;
}

int compute_spanning_trees(int s) {
    mat_size = 0;
    vector<int> nodes;
    for(int i=0; i<n; ++i) if(s & (1<<i)) nodes.push_back(i);
    mat_size = nodes.size();
    for(int i=0; i<mat_size; ++i) {
        int u = nodes[i];
        mat[i+1][i+1] = __builtin_popcount(adj_mask[u] & s);
        for(int j=0; j<mat_size; ++j) {
            int v = nodes[j];
            if(i == j) continue;
            if(adj_mask[u] & (1<<v)) mat[i+1][j+1] = MOD-1;
            else mat[i+1][j+1] = 0;
        }
    }
    mat_size--;
    return determinant();
}

#define FWHT_LOOP for(int i=1; i<(1<<n); i<<=1) for(int j=0; j<(1<<n); j+=(i<<1)) for(int k=j; k<j+i; ++k)

void fwht(int *arr) {
    FWHT_LOOP add(arr[k+i], arr[k]);
}

void ifwht(int *arr) {
    FWHT_LOOP sub(arr[k+i], arr[k]);
}

int main() {
    n = read(); m = read();
    full_mask = (1 << n) - 1;
    for(int i=0; i<m; ++i) {
        int u = read()-1, v = read()-1;
        adj_mask[u] |= (1 << v);
        adj_mask[v] |= (1 << u);
    }

    for(int i=0; i<n; ++i) dp_path[1<<i][i] = 1;
    pow2[0] = 1;
    for(int i=1; i<=n; ++i) add(pow2[i] = pow2[i-1], pow2[i-1]);
    inv[1] = 1;
    for(int i=2; i<=n; ++i) inv[i] = (ll)inv[MOD%i] * (MOD - MOD/i) % MOD;

    // Compute path DP
    for(int s=1; s < (1<<n); ++s) {
        int min_node = __builtin_ctz(s);
        for(int u=min_node; u<n; ++u) {
            if(!dp_path[s][u]) continue;
            for(int v=min_node+1; v<n; ++v) {
                if(s & (1<<v)) continue;
                if(adj_mask[u] & (1<<v)) add(dp_path[s | (1<<v)][v], dp_path[s][u]);
            }
        }
    }

    // Compute cycle counts and generating functions
    gen_func[0][0] = 1;
    for(int s=1; s < (1<<n); ++s) {
        int min_node = __builtin_ctz(s);
        int sz = __builtin_popcount(s);
        gen_func[sz][s] = 1;
        for(int u=0; u<n; ++u) {
            if(s & (1<<u)) gen_func[sz][s] = (ll)gen_func[sz][s] * __builtin_popcount(adj_mask[u] & s) % MOD;
        }

        cycle_count[s] = 0;
        for(int u=min_node+1; u<n; ++u) {
            if(adj_mask[u] & (1<<min_node)) add(cycle_count[s], dp_path[s][u]);
        }
        if(cycle_count[s] % 2) cycle_count[s] += MOD;
        cycle_count[s] >>= 1;
        if(sz <=2) cycle_count[s] =0;
    }

    // Compute FWHT for generating functions
    for(int i=0; i<=n; ++i) fwht(gen_func[i]);

    // Compute logarithmic transform for connected components
    for(int i=1; i<=n; ++i) {
        for(int s=0; s < (1<<n); ++s) ln_func[i][s] = gen_func[i][s];
        for(int s=0; s < (1<<n); ++s) {
            int tmp =0;
            for(int j=1; j<i; ++j) {
                add(tmp, (ll)j * ln_func[j][s] % MOD * gen_func[i-j][s] % MOD);
            }
            sub(ln_func[i][s], (ll)inv[i] * tmp % MOD);
        }
    }

    // Inverse FWHT
    for(int i=0; i<=n; ++i) ifwht(ln_func[i]);

    // Calculate final result
    res =0;
    for(int s=1; s < (1<<n); ++s) {
        int sz = __builtin_popcount(s);
        int current = ln_func[sz][s];
        sub(current, (ll)compute_spanning_trees(s) * (sz-1) % MOD);
        current = (ll)current * pow2[sz] % MOD;
        if(current %2) current += MOD;
        current >>=1;
        for(int u=0; u<n; ++u) {
            if(!(s & (1<<u))) current = (ll)current * (MOD +1 - __builtin_popcount(adj_mask[u] &s)) % MOD;
        }
        add(res, current);
    }

    printf("%d\n", res);
    return 0;
}

Method 3: Bivariate Set Power Series

An alternative approach uses bivariate set power series where terms track both node subsets and edge counts. Taking the logarithm of this series isolates connected components, allowing us to extract uniccylic subgraph contributions. This runs in (O(2^n n^4)) time and is theoretically valid but may not be efficient enough for tight constraints.