# 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)↵
↵
## 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](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)↵
↵
## 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](https://www.cnblogs.com/life-of-a-libertine)↵
↵
Looking forward to your upvote!
