Zeta & Mobius Transform

Neutralized · 2022-03-12 08:13:57 · 个人记录

参(chu)考(chu)：容斥原理与子集卷积（四）

因为一些原因，要回来继续填了 /fad

upd：这个可以代替正常 \text{FWT} 的三重循环，虽然常数小没有我也不知道。至少模板题是这样的。套娃。

\zeta \;:\text{Zeta Transform}

定义函数 f:2^V \to \mathbb{Z} ，其中 V 为 n 元集合， 2^V 为 V 所有子集的集合
定义 \zeta 变换：

(\zeta f)(X)=\sum_{Y \subseteq X} f(Y)

即子集函数和
定义集合映射 g:V \to V_i ，其中 V=\{1,2,3,\dotsb,n\} ， V_i=\{v_1,v_2,v_3,\dotsb,v_n\} ，且 v_i = \begin{cases}1 &\text{if } i \in V \\0 &\text{if } i \notin V\ \end{cases}
所以

(\zeta f)(x_1,\dotsb,x_n)=\sum_{y_1,\dotsb,y_n \in \{0,1\}} f(y_1,\dotsb,y_n)

其中

y_1 \le x_1,y_2 \le x_2, \dotsb , y_n \le x_n

这就是说，如果将集合 X 看作一个 n 位的二进制数，那么 \zeta(X) 也就是求得每一位都小于等于它的数个数

然后参照知乎文章，我们可以写出二进制下的转移：

\zeta_{i}(x_1,\dotsb,x_n)= \begin{cases}\zeta_{i-1}(x_1,\dotsb,x_n) &\text{if } x_j=0 \\\zeta_{i-1}(x_1,\dotsb,x_{j-1},0,x_{j+1},\dotsb,x_n)+\zeta_{i-1}(x_1,\dotsb,x_{j-1},1,x_{j+1},\dotsb,x_n) &\text{if } x_j=1 \end{cases}

应用见下文。

\mu \;:\text{Mobius Transform}

另有 μ 变换的定义：

(\mu f)(X)=\sum_{Y \subseteq X}(-1)^{|X \setminus Y|}f(Y)

当 f=1 时它就是容斥原理

2022.5.8 upd:
对于上面这句话解释一下：

如果

f(X)=\sum_{Y \subseteq X}g(Y)

则

g(X)=\sum_{Y \subseteq X}(-1)^{|X \setminus Y|}f(Y)

证明在上面的l1nk里（OI-Wiki

定义 \text{odd-negation} 变换为

(\sigma f)(X)=(-1)^{|X|}f(X)

那么有如下定理：

定理1：

\zeta = \sigma \mu \sigma\,,\,\mu = \sigma \zeta \sigma.

变换优先级是从右往左。

定理2：

$\text{Proof : }

定理1：

① \zeta = \sigma \mu \sigma\,:

(\zeta f)(X)= \sum_{Y \subseteq X}f(Y)=\sum_{Y \subseteq X}(-1)^{2|X|}f(Y)

=\sum_{Y \subseteq X}(-1)^{|X|+|X \setminus Y|+|Y|}f(Y)

=\sigma (\sum_{Y \subseteq X} (-1)^{|Y|+|X \setminus Y|}f(Y))

=\sigma \mu ((-1)^{|X|}f(X))

=(\sigma \mu \sigma f)(X)

\square.

② \mu = \sigma \zeta \sigma\,:

(\mu f)(X)=\sum_{Y \subseteq X}(-1)^{|X \setminus Y|}f(Y)=\sum_{Y \subseteq X}(-1)^{|X|-|Y|}f(Y)

=\sum_{Y \subseteq X}(-1)^{|X|-|Y|+2|Y|}f(Y)=\sum_{Y \subseteq X}(-1)^{|X|+|Y|}f(Y)

=(-1)^{|X|}\sum_{Y \subseteq X}((-1)^{|Y|}f(Y))

=(\sigma \zeta \sigma f)(X)

\square.

定理2：
暂时有一步没看懂。

\text{Fast}\;\zeta\;\text{Transform in OI}

上述DP柿子可以做到在 O(n\,2^n) 时间计算一个给定集合的子集函数和
具体实现：

vector<int> zeta(/*Full set*/);
for(int i=0;i<=/*Max pow*/;++i)
    for(int j=0;j<=/*Full set*/;++j)
        if(j&(1<<i))
            calc zeta[j] with zeta[j^(1<<i)]

注：在国内貌似更多地叫它高维前缀和或子集前缀和， \text{atcoder} 的 \text{editorial} 称作 \text{fast zeta transform}

事实上，由上面 \text{Mobius Transform} 的定义可以知道求出了 \zeta 变换也就求出了 \mu 变换，所以它可以搞 \text{FMT} （大概明白怎么弄了，还没实现过。）

例题
Atcoder ARC136-D

官方题解
人话翻译

在定义出 x \bigsqcup y 后，如果知道 \zeta \;Transform ，就会发现这是个套了层皮的变换
也就是把 y_i 的值从 \{0,1\} 变成了 \{0,1,2,3,4,5,6,7,8,9\}
更直白地讲，也就是从二进制 \zeta 变换变成了十进制上的 \zeta 变换
对于每个 A_i 统计答案即可

record

变换部分：

static const int lim=pow10(6)-1;
inline void done(){
    ri t=1;
    for(ri i(0);i<=5;++i){
        for(ri j(0);j<=lim;++j)
        if(((j/t)%10)!=9) zeta[j+t]+=zeta[j];
        t=(t<<3)+(t<<1);
    }
}

Atcoder ARC137-D

单独写了一个分析

(a \times 1)(x)=\sum_{d \mid x}a(d)

可以用这个求 Dirichlet Prefix Sum 。

record

筛出 1 \sim n 所有的质数后枚举每个质数，对 kp [kp \le n] 加上 zeta_{k}

这个题也是一道比较裸的 zeta 变换。
具体地，i \operatorname{or} j \le K 可以看作是先作一次 zeta 变换求每个 i 的子集最大/次大值后，对每个 i 的最大+次大取前缀 \max 获得。
那么也就不难写了。

Zeta & Mobius Transform

\zeta \;:\text{Zeta Transform}

\mu \;:\text{Mobius Transform}

\text{Fast}\;\zeta\;\text{Transform in OI}

例题