0%

20200218模拟赛

Jump

题目描述

\(n\) 个点 \(m\) 条边的无向图,求可将每个边定向的方案满足最后的图是 DAG 的方案数 ### 题解

\(f_S\) 为点集为 \(S\) 的方案数,枚举入度为 \(0\) 的点,可得到

\[ f_S=\sum_{T\subseteq S\land T\ne\emptyset}(-1)^{|T|+1}w_Tf_{S-T} \]

其中 \(w_T\) 为点集 \(T\) 内不存在相互之间的边是否为真,因为入度为零即 \(T\rightarrow S-T\) 的边都被定向方案数为 \(1\),由于入度为零那么相互之间必然不能有边

但是我们考虑到对于一个入度为 \(0\) 的集合 \(I\) 而言,它的每个子集实际上都把它算了一遍,所以我们要算上容斥系数 \((-1)^{|I|+1}\) 具体来说,我们考虑

\[ \sum_{J\subseteq I}a_J=[I\ne\emptyset] \]

用子集反演得到

\[ a_I=\sum_{J\subseteq I}(-1)^{|I-J|}[J\ne\emptyset] \]

化简得

\[ a_I=\sum_{i=1}^{|I|}\binom{|I|}{i}(-1)^{|I|-i} \]

即当 \(I\) 不为空时

\[ a_I=(-1)^{|I|+1} \]

然后就是标准的子集卷积,FWT 可以在 \(\operatorname{O}(n^22^n)\) 的解决,注意取模的常数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;
typedef long long int64;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
return f*x;
}
const int N = 2e1+5, S = 1<<20|5, P = 1e9+7;
int n, m, e[N], c[S], f[N][S], g[N][S];
void add(int &x, int y) { x = x+y<P?x+y:x+y-P; }
void FWT(int *A, int n, int t)
{
for(int mid = 1; mid < n; mid <<= 1)
for(int j = 0, len = mid<<1; j < n; j += len)
for(int k = 0; k < mid; ++k)
if(!t) add(A[j+k+mid], A[j+k]);
else add(A[j+k+mid], P-A[j+k]);
}
int W(int s) { for(int i = 0; i < n; ++i) if((s>>i&1)&&c[e[i]&s]) return 0; return (c[s]&1)?1:P-1; }
int main()
{
freopen("jump.in", "r", stdin), freopen("jump.out", "w", stdout);
n = read(), m = read();
for(int i = 1; i <= m; ++i)
{
int x = read()-1, y = read()-1;
e[x] |= 1<<y, e[y] |= 1<<x;
}
for(int s = 1; s < 1<<n; ++s) c[s] = c[s>>1]+(s&1), g[c[s]][s] = W(s);
f[0][0] = 1, FWT(f[0], 1<<n, 0);
for(int i = 1; i <= n; ++i) FWT(g[i], 1<<n, 0);
for(int i = 1; i <= n; ++i)
for(int j = 0; j < i; ++j)
for(int s = 0; s < 1<<n; ++s)
add(f[i][s], 1ll*f[j][s]*g[i-j][s]%P);
FWT(f[n], 1<<n, 1), printf("%d\n", f[n][(1<<n)-1]);
return 0;
}