題目描述
求一張有向圖的強連通生成子圖的數目對 $10^9+7$ 取模的結果。
題解
狀壓dp+容斥原理
設 $f[i]$ 表示點集 $i$ 強連通生成子圖的數目，容易想到使用總方案數 $2^{sum[i]}$ 減去不為強連通圖的方案數得到強連通圖的方案數，其中 $sum[i]$ 表示點集 $i$ 中邊的數目。
考慮什么樣的圖不是強連通圖：縮點后入度為0的強連通分量對應的點集不是全集。
枚舉這些入度為0的強連通分量對應的點集，由于無法保證只有這些點構成的入度為0的強連通分量，因此需要進一步容斥。推之可以發現容斥系數與這些點形成的強連通分量數目的奇偶性有關。
更具體來講，形成奇數個強連通分量時容斥系數為正（即減去），形成偶數個強連通分量為負（即加上）。
設 $g[i]=i個點形成奇數個強連通分量的方案數-i個點形成偶數個強連通分量的方案數$ ，那么枚舉 $i$ 中編號最小的點所在連通塊 $i-j$ （即枚舉剩下部分 $x$ 不與編號最小的點相連的強連通分量 $j$ ），則有 $g[i]=-\sum\limits_{j\subset x}f[i-j]·g[j]$ 。注意此時的 $g$ 不包含 $i$ 只形成一個強連通分量的情況，以便下面 $f$ 的容斥。
那么枚舉欽定的入度為0的強連通分量 $j$ ，就有 $f$ 的轉移：$f[i]=2^{sum[i]}-\sum\limits_{j\subset i}2^{sum[i]-w[j]}·g[j]$ ，其中 $w[j]$ 表示 $i$ 向 $j$ 連邊的數目，表示欽定的點不能被連邊，其它的隨意連。
最后將只有一個強連通分量的方案 $f[i]$ 算進 $g[i]$ 。
答案就是 $f[2^n-1]$ 。
時間復雜度 $O(3^n)$?
#include <cstdio>
#define N 32775
#define mod 1000000007
typedef long long ll;
int in[N] , out[N] , cnt[N] , sum[N] , w[N];
ll b[215] , f[N] , g[N];
void dfs(int i , int j)
{if(i & (j - 1)) dfs(i , i & (j - 1));w[j] = w[j - (j & -j)] + cnt[in[j & -j] & i];
}
int main()
{int n , m , i , j , x , y;scanf("%d%d" , &n , &m);b[0] = 1;for(i = 1 ; i <= m ; i ++ ){scanf("%d%d" , &x , &y) , x -- , y -- ;in[1 << y] |= 1 << x , out[1 << x] |= 1 << y;b[i] = b[i - 1] * 2 % mod;}for(i = 1 ; i < (1 << n) ; i ++ ){x = i - (i & -i) , cnt[i] = cnt[x] + 1 , sum[i] = sum[x] + cnt[in[i & -i] & i] + cnt[out[i & -i] & i] , f[i] = b[sum[i]];dfs(i , i);for(j = x ; j ; j = x & (j - 1)) g[i] = (g[i] - f[i ^ j] * g[j] % mod + mod) % mod;for(j = i ; j ; j = i & (j - 1)) f[i] = (f[i] - b[sum[i] - w[j]] * g[j] % mod + mod) % mod;g[i] = (g[i] + f[i]) % mod;}printf("%lld\n" , f[(1 << n) - 1]);return 0;
}
?
...)
