炫酷反演魔术 魔术揭秘

刚才的标题是唬人的…

请允许我先丢个链接,然后开始扯淡.

开场

vfk老师在这份课件中深入浅出地讲解了各种OI中常用的反演,本蒟蒻表示并没有完全看懂(尤其是对于矩阵的一部分知识不是非常熟悉),而且由于网上关于反演的资料除了莫比乌斯反演之外非常少,所以本蒟蒻在这里只是谈谈个人对反演的理解,如果出现了错误还请各路神犇不吝赐教.

还有就是课件中的推导已经写得非常漂亮了,我也没必要在这里再自己敲一遍(所以写这篇博客的目的何在?),有些地方还是直接”抛结论跑”好了.

揭秘

反演的思路是用未知量表示已知量,然后反过来推出未知量的表达式.下面我们默认表示已知量,表示未知量.

课件中介绍了二项式反演,莫比乌斯反演,子集反演等等,这些反演都与容斥原理有着密不可分的关系,就是说都可以用容斥来偏”意识流”地理解.但是不管怎么说,用反演来推导显得比较有说(zhuang)服(bi)力(fan).

推导反演的过程,就是”找到了一个if语句,说了一句废话,代进去搞搞居然就凑出来了个”.当然这其中需要很多技巧,可以通过看课件中的推导来体会.

二项式反演

推导的if语句是.

说的废话是.

莫比乌斯反演

一个方向:

另一个方向:

说实话我并不知道反方向的是怎么推的,但是结论非常好记.

if语句:.

废话:.

子集反演

一个方向:

另一个方向:

还是只会推正方向的…

if语句:.

废话:.

话说从这里开始变量名就有点奇怪了呢...

这个推导和二项式反演的推导非常相似.

实际运用时,这个东西可以用高维前缀和的写法来做,具体看下面的”卷积”部分.

离散傅里叶变换

这个东西实质上也是反演…但是我并不会用反演推…

给的if语句是.

然而我并不知道该说什么废话…

不过课件里那个”又一道经典题”是可以用这个if语句推的.

or卷积

给定,求:

关于这个名称应该没有正规的定义吧…似乎这个和下面的那个卷积都应该是”子集卷积”?还是看个人理解吧,我比较偏向于专门把下面的那个卷积称为”子集卷积”.

不管怎样,这个卷积是子集反演的一个经典应用.

令,类似地定义,可以推导出,求出后用子集反演求出.

具体实现时,直接略无脑地用高维前缀和正着倒着搞就可以实现子集反演了,复杂度是.

另外,卷积可以直接先把集合取补集转化成卷积来做.

Code

void or_conv(){
    rep(i,,n)rep(j,,<<n)if(j&<<i){
        A[j]+=A[j^<<i];
        B[j]+=B[j^<<i];
    }
    rep(i,,<<n)C[i]=A[i]*B[i];
    rep(i,,n)rep(j,,<<n)if(j&<<i)
        C[j]-=C[j^<<i];
}
           

子集卷积

给定,求:

[Math Processing Error]

这个…似乎课件上的推导有些问题(当然很有可能是我没看懂),这里良心地写一下我的推法.

如果直接用交集和并集的限制是推不出来的,我们必须再加一个维度.

令[Math Processing Error],

还有[Math Processing Error].

那么:

然后再用子集反演,可以推出:

最终答案就是.

这样复杂度就可以做到了.

但是直接暴力做,复杂度是,凭借极小的常数在时仍可以碾压标程….

Code

const int N=,M=<<N;

int n,bitcnt[M],A[M],B[M],C[M],sum_A[N+][M],sum_B[N+][M],sum_C[N+][M];

inline void init(){
    rep(i,,M)bitcnt[i]=bitcnt[i>>]+(i&);
}
void conv(){

    rep(i,,n+)rep(j,,<<n){
        if(i==bitcnt[j]){
            sum_A[i][j]=A[j];
            sum_B[i][j]=B[j];
        }
        else sum_A[i][j]=sum_B[i][j]=;
    }

    rep(i,,n)rep(j,,<<n)if(j&<<i)rep(k,,bitcnt[j]){
        mod_add(sum_A[k][j],sum_A[k][j^<<i]);
        mod_add(sum_B[k][j],sum_B[k][j^<<i]);
    }

    rep(i,,n+)rep(j,,<<n){
        sum_C[i][j]=;
        rep(k,,i+)sum_C[i][j]=(sum_C[i][j]+ll*sum_A[k][j]*sum_B[i-k][j])%mod;
    }

    rep(i,,n)rep(j,,<<n)if(j&<<i)rep(k,,n+)
        mod_minus(sum_C[k][j],sum_C[k][j^<<i]);

    rep(i,,<<n)C[i]=sum_C[bitcnt[i]][i];

}
           

收场

妈呀最怕这种时候要我总结点什么了！

大概我对反演的理解也就是这些了…

我觉得学习反演,不应该只记个结论,中间的推导过程也是很有价值的.

那就先这样吧.