# Set algorithm↵
↵
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}$.↵
↵
#### OR FWT/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 FWT/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.↵
↵
## 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!
↵
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}$.↵
↵
#### OR FWT/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 FWT/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.↵
↵
## 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!
