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

code

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.

code

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

Others

My Blog

Looking forward to your upvote!