Inverse Fast Möbius Transform

The Inverse Fast Möbius Transform is an algorithm that finds a function $g$ such that $\forall S\subseteq \{0,1,\dots ,n-1\},{\sum }_{T\subseteq S}g(T)=f(S)$ in $\mathcal{O}(n{2}^n)$ time and $\mathcal{O}(1)$ space.

Algorithm

Lemma

$$g(S)=\sum _{T\subseteq S}(-1{)}^{|S|-|T|}f(T)$$

is a function such that $\forall S\subseteq \{0,1,\dots ,n-1\},{\sum }_{T\subseteq S}g(T)=f(S)$.

Proof

$$\begin{array}{rl}\sum _{T\subseteq S}g(T)& =\sum _{T\subseteq S}\sum _{Q\subseteq T}(-1{)}^{|T|-|Q|}f(Q)\\ & =\sum _{Q\subseteq S}f(Q)\sum _{Q\subseteq T\subseteq S}(-1{)}^{|T|-|Q|}\\ & =\sum _{Q\subseteq S}f(Q)\sum _{T\subseteq S\setminus Q}(-1{)}^{|T|}\\ & =\sum _{Q\subseteq S}f(Q)\sum _{k=0}^{|S\setminus Q|}\left(\genfrac{}{}{0ex}{}{|S\setminus Q|}{k}\right)(-1{)}^k\\ & =\sum _{Q\subseteq S}[|S\setminus Q|=0]f(Q)\\ & =f(S)\end{array}$$

0. Apply the Fast Möbius Transform to find ${\sum }_{T\subseteq S}(-1{)}^{|T|}f(T)$ for each subset $S$ of $\{0,1,\dots ,n-1\}$.
1. Apply the lemma to find $g$.

This algorithm solves the problem in $\mathcal{O}(n{2}^n)$ time and $\mathcal{O}(1)$ space.

void ifmt(int n, std::vector<int> &a) {
	for (u32 s = 0u; s < 1u << n; s++) {
		if (std::popcount(s) % 2 == 1) {
			a[s] *= -1;
		}
	}
	fmt(n, a);
	for (u32 s = 0u; s < 1u << n; s++) {
		if (std::popcount(s) % 2 == 1) {
			a[s] *= -1;
		}
	}
}