Description
输入格式
输出格式
样例
数据范围与提示
Solution
以下问题均在有向图上进行考虑。
首先我们可以考虑如何计算一个点集的是 DAG 完全子图个数。设这个叫 (D(S)) ,定义 (w(S,T)) 表示 (S o T) 的边数,(h(S)) 为 (w(S,S))。
我们可以枚举哪些点入度为 (0),那么我们可以通过容斥得到转移式:
[D(S)=2^h(S)-sum_{T subset S} (-1)^{|T|+1}D(Sotimes T)2^{w(T,Sotimes T)}
]
考虑到原问题。我们设 (f(S)) 表示集合 (S) 的是 scc 的完全子图个数,(g(S)) 表示将 (S) 分成奇数个 scc 的方案数减去偶数个 scc 的方案数。(原因见上式)
同样的,我们可以枚举哪些 scc 在缩点后的图上入度为 (0) ,可以得到转移式:
[f(S)=2^h(S)-sum_{Tsubseteq S}g(T)2^{w(T,Sotimes T)}2^{h(Sotimes T)}
]
[g(S)=f(S)-sum_{Tsubset S} f(Sotimes T) imes g(T)
]
不过需要注意的是你在计算 (g(S)) 的时候需要钦定一下顺序,否则会算重,具体来说可以每次当前的 scc 都必须包含一个固定点。
Code
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define mod 1000000007
#define MAXN 17
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
template <typename T> inline void chkmax (T &a,T b){a = max (a,b);}
template <typename T> inline void chkmin (T &a,T b){a = min (a,b);}
int n,m,pw[MAXN * MAXN],toS[MAXN],lg[1 << 16],siz[1 << 16],cnt[1 << 16],f[1 << 16],g[1 << 16];
int mul (int a,int b){return 1ll * a * b % mod;}
int dec (int a,int b){return a >= b ? a - b : a + mod - b;}
int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;}
void Sub (int &a,int b){a = dec (a,b);}
void Add (int &a,int b){a = add (a,b);}
int lowbit (int x){return x & (-x);}
int getw (int S1,int S2){
int res = 0;
while (S1){
int now = lowbit(S1);
S1 -= now,now = lg[now] + 1;
res += siz[toS[now] & S2];
}
return res;
}
signed main(){
read (n,m),pw[0] = 1;
for (Int i = 1;i <= m;++ i) pw[i] = add (pw[i - 1],pw[i - 1]);
for (Int i = 1;i < n;++ i) lg[pw[i]] = i;
for (Int S = 0;S < (1 << n);++ S) siz[S] = siz[S >> 1] + (S & 1);
for (Int i = 1,u,v;i <= m;++ i) read (u,v),toS[u] |= (1 << v - 1);
for (Int S = 0;S < (1 << n);++ S) cnt[S] = getw (S,S);
for (Int S = 1;S < (1 << n);++ S){
int nS = S ^ lowbit(S);
for (Int T = nS;T;T = (T - 1) & nS) Sub (g[S],mul (f[S ^ T],g[T]));
f[S] = pw[cnt[S]];
for (Int T = S;T;T = (T - 1) & S) Sub (f[S],mul (g[T],mul (pw[getw (T,S ^ T)],pw[cnt[S ^ T]])));
Add (g[S],f[S]);
}
write (f[(1 << n) - 1]),putchar ('
');
return 0;
}