炫酷反演魔術 魔術揭秘

剛才的标題是唬人的…

請允許我先丢個連結,然後開始扯淡.

開場

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];

}
           

收場

媽呀最怕這種時候要我總結點什麼了！

大概我對反演的了解也就是這些了…

我覺得學習反演,不應該隻記個結論,中間的推導過程也是很有價值的.

那就先這樣吧.