春姬的炫酷反演魔术

二项式反演的推法是什么?

$f(n)=\sum_{k=0}^n\binom{n}{k}g(k)$

$g(n)=\sum_{k=0}^n\binom{n}{k}(-1)^{n-k}f(k)$

我们说句废话

$g(n)=\sum_{k=0}^n\binom{n}{k}[n-k==0]g(i)$

然后对于上式中[n-k==0],进行二项式展开

即利用 $[n==0]=\sum_{i=0}^n(-1)^i\binom{n}{i}$

就有了

循环节长度为n的字符串个数, $n<=1e9$

莫比乌斯反演

$f(n)=26^n$ ,长度为n随便字符串

$g(n)=\sum_{d|n}\mu(\frac{n}{d})f(d)$

g(n)就是答案

根据这个以及我们观察可知:

对于形式 $f(n)=\sum_{k,n}a_{n,k}*g(k)$

可以有一套定式的

$g(k)=\sum_{k,n}\mu(n,k)f(n)$

来反演内层函数g

其中我们一定有 $\sum_{k=1}^na_{n,k}\mu(k,m)=[n==m]$

~~这个魔术等于没变,因为这个 $\mu$ 显然不好求qwq~~

于是我们想写成矩阵的形式,你会发现这个等价于求下三角矩阵的逆矩阵

下三角矩阵求逆是 $O(n^2)$ 的,因为只需要高斯消元的时候上界枚举到对角线下界枚举到i就好了

因为显然根据一开始写成的式子,无论是二项式反演还是莫反都只是一个f的一列数*矩阵=g的一列数

那不妨我们放一只例题

\sum_{j=1}^ngcd(i,j)^c*lcm(i,j)^dx_j\equiv b_i(\mod p)

$n<=1e3?$

$n<=1e5?$

前者显然可以构建矩阵,然后mod意义下矩阵求逆

后者?老老实实反演吧

\sum_{i=1}^ngcd(i,j)^{c-d}i^dj^dx_j\equiv b_i

我们可以推出

\sum_{t|i}d^c\sum_{j=1}^{\lfloor\frac{n}{t}\rfloor}\sum_{pt|i,p|j}\mu(p)i^dj^dx_{jd}=b_i

考虑交换位置,我们把i^d这个东西除过去

\sum_{T|i}\sum_{t|T}t^c\mu(T/t)\sum_{j=1}^{\frac{n}{T}}j^dx_{jT}\equiv b_i/g(i)

$g(i)=i^d$

坏了,我们现在已知到右边,想求左边,这怎么办?

反演啊

我们显然可以写成

\sum_{T|i}f(T)z(T)=b_i/g(i)

我们已经知道右边,想求左边,莫反他有

$f(T)z(T)=\sum_{q|T}b_q/g(q)$

然后我们有了 $f(T)z(T)$

显然的是,这个f怎么都能 $O(n poly(log))$ 预处理

然后我们有这个z了

$z(T)=\sum_{j=1}^{\frac{n}{T}}(j)^dx_{jT}$

坏坏了,我们现在已知到右边,想求左边,这怎么办?

魔术啊

我们把第一项单独拿出来

$h(d)x_d=z_d-\sum_{j=1}^n[j>d][d|j]h_j*x_j$

你会发现第一项有了,后面那个东西啊显然可以从后向前 $O(nlogn)$ 求出来,因为d的倍数是调和级数呢

所以就做完了

总而言之,反演就完了

当然,你会发现第二歩很通式,我们尝试用它解下第一步

$\sum_{T|i}f(T)z(T)=b_i/g(i)$

分裂

$f(i)z(i)=b_i/g(i)-\sum_{T|i,T>i}f(T)z(T)$

同样使用调和级数,即

for (int i = 1; i <= n; i++)
    f_z[i] = b[i] / g(i);
for (int i = 1; i <= n; i++)
    for (int j = i + i; j <= n; j += i)
        f_z[j] -= f_z[i];

子集反演(就是裸容斥)

$f(S)=\sum_{T\in S}g(T)$

$g(S)\sum_{T \in S}(-1)^{|S|-|T|}f(T)$

eg:

A,B数组长度为 $2^n-1$

$C_i=\sum_{j|k=i}A_jB_k$

问C,n<=20

:"考虑FWT"

考虑你不会FWT

我们要转换条件

恰好或起来为i,等价于或起来至多为i,然后容斥qwq

定义 $a'=\sum_{p \in S}a_p$ 注意到 $c'=a'*b'$

因为 $[p∪q\in S]=[p\in S][q\in S]$

怎么求c?

~~暴力枚举~~

逆高维前缀和即可

高维前缀和是把每一维向前推的过程

~~逆高维前缀和就是把每一维差分回来的过程~~

就是把+变成-

为什么对?

等价于子集反演

如果用莫反,我们甚至可以实现 $r=gcd(p,q),lcm$ 之类的

多重子集反演

允许多个元素出现组成集合

$f(S)=\sum_{T \in S}g(T)$

定义 $\mu(S)$ 是S中包容重复元素时为0,否则为 $|-1|^{|S|}$

$\sum_{T \in S}\mu(T)=[S=0]$

$g(S)=\sum_{T\in S}\mu(S-T)f(T)$

~~FFT~~

的模板题如何反演的视角解释?

定义zhq为单位根

$\sum_{k=0}^{n-1}zhq^{vk}=\frac{1-zhq^{nvk}}{1-zhq^{vk}}=0$

等于0是显然的

如果有ljh的数学知识,你就会意识到当公比为1的时候要特判!

$\frac{1}{n}\sum_{k=0}^{n-1}zhq^{vk}=[v mod n==0]$

利用上式变魔术

$[(p+q-r)mod n = 0]=\frac{1}{n}\sum_{k=0}^{n-1}zhq^{-rk}zhq^{pk}zhq^{qk}$

$c_r=\frac{1}{n}\sum_{k=0}^{n-1}zhq^{-rk}\sum_{p,q}zhq^{pk}a_pzhq^{qk}b_q$

$c_r=\frac{1}{n}\sum_{k=0}^{n-1}zhq^{-rk}\sum_{p}zhq^{pk}a_p\sum_qzhq^{qk}b_q$

哼,反演

$f_m=\sum_{k=0}^{m-1}zhq^{mk}g_k$

$g_m=\frac{1}{n}\sum_{k=0}^{n-1}zhq^{-mk}f_k$

多项式乘法就相当于算出一式这个f的乘积,然后根据二式再反演出g就是c数组

and卷积?n<=20

$[p~and~q=r]=[!p~|~!q \in ~!r]$

其实挺蠢的

子集卷积

$c_r=\sum_{p \in r}a_pb_{r~xor~p}$

$n<=18$

~~数据范围有了些许不同~~

等价于 $[p and q=0][p | q=r]$

等价于 $[!p|!q\in 2^n-1][p|q=r]$

你又废了,我也不知道可不可行

我们多定义一维i,表示|S|=i的集合的卷积

$\sum_{p\in r}[|p|=i]a_pb_{r xor p}$

注意我们对于或要枚举r的一个子集v,然后满足

$c_{r,i}=\sum_{v \in r}(-1)^{|r|-|v|}\sum_{p,q \in v}[|p|=i][|q|=|r|-i]a_pb_q$

这个式子还不简单?处理 $a'_{p,i}=\sum_{s \in p}[|S|=i]a_s$

$n^22^n$

逆,高维前缀和秒一切

GG!

其实我们就是重糊了FWT和FFT,而且子集卷积更菜

感觉学到不多?不可能💢

夏晓光(loveJY)的博客

碧翠丝的动态树