P11714 [清華集訓 2014] 主旋律

pref

怎么新賽季就開始了。

一直想補歲月，但至今沒有實現(xiàn)，也就只好先從主旋律下手。

我該在哪里停留？我問我自己。

sol

題意就是求刪后原圖仍強聯(lián)通的有向邊刪邊方案數(shù)。

強聯(lián)通是不好刻畫的，考慮非強聯(lián)通。不難發(fā)現(xiàn)，其滿足縮點之后是一個 DAG，先從 DAG 下手。

考慮刻畫 DAG，不難想到拓撲，從而考慮到可以從入度為 \(0\) 的點入手，這些點刪完之后得到的圖仍然是 DAG，于是可以考慮從這里入手 DP。

令點集 \(S\) 的生成 DAG 方案數(shù)為 \(dp(S)\)，記 \(f(T)\) 表示 \(S\) 內(nèi)有且僅有 \(T\) 點集中的點入度為 \(0\) 的方案數(shù)，則有轉(zhuǎn)移：

容斥求 \(f\)，記 \(g(T)\) 為欽定 \(T\) 點集中的點入度為 \(0\) 的方案數(shù)，\(E_{S,T}\) 為 \(S\) 點集連向 \(T\) 點集的邊數(shù)，顯然有：

則有：

計算 \(dp(S)\)：

考慮拓展到縮點前的原圖上，記 \(dp(S)\) 表示 \(S\) 是個 SCC 的方案數(shù)，\(g(T)\) 表示欽定 \(T\) 中點縮成若干入度為 \(0\) 的點的方案數(shù)，我們嘗試仿照上面的式子寫轉(zhuǎn)移式，但不難發(fā)現(xiàn)容斥系數(shù)無法得到，其原因是無法得知 \(T\) 中的點到底縮成了幾個入度為 \(0\) 的點。

考慮把容斥系數(shù)融入到 \(g\) 的定義中去，那么 \(g(S)\) 表示 \(S\) 中點縮成奇數(shù)個入度為 \(0\) 的點的方案數(shù)減去 \(S\) 中點縮成偶數(shù)個入度為 \(0\) 的點的方案數(shù)的值。在此之后求 \(g\) 其實也沒有變得很困難，欽定一個子集視作新加入的來轉(zhuǎn)移即可，強制令其包含 \(S\) 中某一個定點，比如 \(\mathrm{lowbit}(S)\) 代表元素，即可得到：

也就是縮成一個 SCC 的方案數(shù)，減去新加 SCC 的方案數(shù)。后者是因為新加一個塊塊數(shù)奇偶性改變，相當于乘了一個容斥系數(shù) \(-1\)。

得到 \(g\) 之后即可得到 \(dp\)：

特別的，當 \(S=T\) 時，\(g(S)\) 此時不應(yīng)加上 \(dp(S)\)，考慮組合意義理解一下即可。那么就是先算 \(g(S)\) 不加上 \(dp(S)\)，再算得 \(dp(S)\)，最后給 \(g(S)\) 加回去即可。

然后壓力給到 \(E\) 的計算，這個東西現(xiàn)在狀態(tài)數(shù) \(4^n\)，成為了瓶頸。然而不難發(fā)現(xiàn)，我們只會用到 \(E_{S,S},E_{T,S-T}\) 這兩種形式的狀態(tài)，故而狀態(tài)數(shù)實際上只需要 \(3^n\)。考慮隨 \(S\) 動態(tài)更新這兩個東西，定義 \(I_v\) 為連向點 \(v\) 的點集，\(O_v\) 為點 \(v\) 連向的點集，每次欽定集合內(nèi)一個點 \(u\)（比如 \(\mathrm{lowbit}\)）轉(zhuǎn)移即可，有：

于是這個問題結(jié)束了。最后復(fù)雜度為 \(O(3^n)\)。

code

const int N=15,S=1<<N;

int n,m;
int out[N],in[N],lg[S],e1[S],e2[S];
mint f[S],g[S],pt[N*N];

inline void Main(){
    cin>>n>>m;
    pt[0]=1;rep(i,1,n*n)pt[i]=pt[i-1]*2;
    lg[1]=0;
    rep(i,2,1<<n-1)lg[i]=lg[i>>1]+1;
    rep(i,1,m){
        int a,b;cin>>a>>b;--a,--b;
        out[a]|=1<<b;in[b]|=1<<a;
    }
    repl(s,1,1<<n){
        int x=s&-s;
        e2[s]=e2[s^x]+__builtin_popcount(s&in[lg[x]])+__builtin_popcount(s&out[lg[x]]);
    }
    repl(s,1,1<<n){
        e1[s]=0;
        for(int t=s-1&s;t;t=t-1&s){
            int x=s-t&t-s;
            e1[t]=e1[t|x]-__builtin_popcount(s-t&out[lg[x]])+__builtin_popcount(t&in[lg[x]]);
        }
        for(int t=s-1&s;t;t=t-1&s){
            if((s&-s)!=(t&-t))continue;
            g[s]-=f[t]*g[s^t];
        }
        f[s]=pt[e2[s]];
        for(int t=s;t;t=t-1&s)f[s]-=g[t]*pt[e1[t]+e2[s^t]];
        g[s]+=f[s];
    }
    put(f[(1<<n)-1]);
}