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)\) 的解决，注意取模的常数即可

#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;
}