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.,
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$$$,
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
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
We difine the addition on $$$(S\rightarrow V)$$$ is addition on each on single element.
And its invertion transform is easy to find.
$$$\textrm{FWT}^{-1}$$$ a.k.a inverse Mobius Transform.
And verify the Pointwise product property.
Afterwards,I will omit some details.
AND FWT/FMT
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];
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)$$$
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);
}
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
the inverse
Fast Subset Convolution
define
one can show that
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
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
QOJ13083
We see if $$$f(P)$$$ is certain,the mask of $$$P$$$ is easier to describe.
now the $$$f(P),f(Q)$$$ is limited by $$$S,T$$$,so enumerate $$$S,T$$$.
Do the FWT convolution (OR) $$$\hat{f}\times \hat{f}$$$
and handle some details.
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$$$ 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.
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.
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
Looking forward to your upvote!
