# 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: ↵
↵
1. Invertibility: $\text{FWT}$ has an inverse map $\text{FWT}^{-1}$. ↵
↵
2. Efficiency: $\text{FWT}$ can be computed in $O(n \log n)$ time. ↵
↵
3. 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}$.↵
↵
#### ORFWT/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.↵
↵
#### ANDFWT/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/FMT↵
↵
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|<|S| \\↵
1 & \text{if } |U\cup V|=|S| < 0↵
\end{cases}↵
$$↵
↵
times.↵
↵
So it's right.↵
↵
### Online Convolution (Luogu4221)↵
↵
Let begin with the problem. [P4221 [WC2018] 州区划分 — 洛谷](https://www.luogu.com.cn/problem/P4221)↵
↵
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](https://mirror.codeforces.com/contest/1713/submission/334276279)↵
↵
### 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](https://qoj.ac/submission/1232959)↵
↵
## 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:↵
↵
1. $f\leftarrow h$ , a root connected to a tree↵
2. $f\leftarrow g$ a cycle is closed.↵
3. $g\leftarrow h$ extend the chain↵
4. $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](https://qoj.ac/submission/1824562)↵
↵
#### 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](https://www.luogu.com.cn/record/220441400)↵
↵
## References↵
↵
https://mirror.codeforces.com/blog/entry/45223↵
↵
https://mirror.codeforces.com/blog/entry/72488↵
↵
https://www.luogu.com.cn/problem/P4717↵
↵
https://people.csail.mit.edu/rrw/presentations/subset-conv.pdf↵
↵
https://www.luogu.com.cn/article/gs78uwd7↵
↵
https://www.cnblogs.com/Mackerel-Pike/p/16395436.html↵
↵
https://yhx-12243.github.io/OI-transit/records/loj6719%3Bgym102331C.html↵
↵
## Others↵
↵
[My Blog](https://www.cnblogs.com/life-of-a-libertine)↵
↵
Looking forward to your upvote! 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>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;↵
```↵
↵
# References↵
↵
https://mirror.codeforces.com/blog/entry/45223↵
↵
https://mirror.codeforces.com/blog/entry/72488↵
↵
https://www.luogu.com.cn/problem/P4717↵
↵
https://people.csail.mit.edu/rrw/presentations/subset-conv.pdf↵
↵
https://www.luogu.com.cn/article/gs78uwd7↵
↵
https://www.cnblogs.com/Mackerel-Pike/p/16395436.html↵
↵
https://yhx-12243.github.io/OI-transit/records/loj6719%3Bgym102331C.html↵
↵
APIO 2025 Class: 【陈昕阳】集合幂级数在子图计数问题上的应用.pdf↵
↵
吕凯风(vfleaking)，集合幂级数的各种应用及其快速算法，中国国家集训队论文2015.↵
↵
https://www.cnblogs.com/alex-wei/p/set_power_series.html↵
↵
https://www.cnblogs.com/tzcwk/p/dxs-sqr.html↵
↵
## Others↵
↵
[My Blog](https://www.cnblogs.com/life-of-a-libertine)↵
↵
[good code](https://www.luogu.com.cn/record/260322274)
↵
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.↵
↵
↵
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}$↵
↵
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: ↵
↵
1. Invertibility: $\text{FWT}$ has an inverse map $\text{FWT}^{-1}$. ↵
↵
2. Efficiency: $\text{FWT}$ can be computed in $O(n \log n)$ time. ↵
↵
3. 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
↵
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$$↵
↵
↵
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
↵
$$\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$$↵
↵
↵
\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.↵
↵
↵
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|<|S| \\↵
1 & \text{if } |U\cup V|=|S| < 0↵
\end{cases}↵
$$↵
↵
times.↵
↵
So it's right.↵
↵
### Online Convolution (Luogu4221)↵
↵
Let begin with the problem. [P4221 [WC2018] 州区划分 — 洛谷](https://www.luogu.com.cn/problem/P4221)↵
↵
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](https://mirror.codeforces.com/contest/1713/submission/334276279)↵
↵
### 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](https://qoj.ac/submission/1232959)↵
↵
## 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)$.↵
↵
↵
↵
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:↵
↵
1. $f\leftarrow h$ , a root connected to a tree↵
2. $f\leftarrow g$ a cycle is closed.↵
3. $g\leftarrow h$ extend the chain↵
4. $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](https://qoj.ac/submission/1824562)↵
↵
#### 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](https://www.luogu.com.cn/record/220441400)↵
↵
#
↵
https://mirror.codeforces.com/blog/entry/45223↵
↵
https://mirror.codeforces.com/blog/entry/72488↵
↵
https://www.luogu.com.cn/problem/P4717↵
↵
https://people.csail.mit.edu/rrw/presentations/subset-conv.pdf↵
↵
https://www.luogu.com.cn/article/gs78uwd7↵
↵
https://www.cnblogs.com/Mackerel-Pike/p/16395436.html↵
↵
https://yhx-12243.github.io/OI-transit/records/loj6719%3Bgym102331C.html↵
↵
## Others↵
↵
[My Blog](https://www.cnblogs.com/life-of-a-libertine)↵
↵
Looking forward to your upvote!
↵
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>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;↵
```↵
↵
# References↵
↵
https://mirror.codeforces.com/blog/entry/45223↵
↵
https://mirror.codeforces.com/blog/entry/72488↵
↵
https://www.luogu.com.cn/problem/P4717↵
↵
https://people.csail.mit.edu/rrw/presentations/subset-conv.pdf↵
↵
https://www.luogu.com.cn/article/gs78uwd7↵
↵
https://www.cnblogs.com/Mackerel-Pike/p/16395436.html↵
↵
https://yhx-12243.github.io/OI-transit/records/loj6719%3Bgym102331C.html↵
↵
APIO 2025 Class: 【陈昕阳】集合幂级数在子图计数问题上的应用.pdf↵
↵
吕凯风(vfleaking)，集合幂级数的各种应用及其快速算法，中国国家集训队论文2015.↵
↵
https://www.cnblogs.com/alex-wei/p/set_power_series.html↵
↵
https://www.cnblogs.com/tzcwk/p/dxs-sqr.html↵
↵
## Others↵
↵
[My Blog](https://www.cnblogs.com/life-of-a-libertine)↵
↵
[good code](https://www.luogu.com.cn/record/260322274)
