题解：CF1193A Amusement Park

· · 题解

更好的阅读体验

我不会图计数。

发现题解区没有正着推容斥系数的，那我就来发一个。

首先注意到，一个 DAG 把所有边的方向取反后得到的也是 DAG。所以所有方案要期望要反转的边数为 \frac{m}{2}。问题转化成将图上一些边反转，形成 DAG 的方案数计数。

考虑 f_{S} 为将 S 点集的导出子图定向成 DAG 的方案数。由于 DAG 有优良的性质，即去掉所有入度为 0 的点后还是 DAG。我们考虑选取一个入度为 0 的集合。因为入度为 0，因此这个集合中不能有连边，即是一个独立集。

以下的描述中都默认 \boldsymbol {T,R} 满足独立集的条件。

转移考虑容斥。假设 g_T 为恰好 T 中的元素入度为 0 的方案数，h_T 为钦定 T 中的元素入度为 0 的方案数。不难发现，

f_{S} = \sum _{T \sube S \land T \not = \varnothing}g_T

又因为在 h 的定义中，我们只是钦定 T 中点入度为 0，因此方案数为将剩余点形成 DAG 的方案数，即

h_T = f_{S - T}

又因为 g_T 的定义是恰好，因此 h_T 就等于所有满足 T \sube R 的 g_R 之和：

h_T = \sum _{T \sube R} g_R

至此是一个子集反演的形式，可以得到：

g_R = \sum _{T \sube R} (-1)^{|R|-|T|}h_T

这个时候代回第一个式子，可以得到：

\begin{align} f_{S} &= \sum _{T \sube S \land T \not = \varnothing}g_T \nonumber \\ &= \sum _{T \sube S \land T \not = \varnothing}\sum _{T \sube R} (-1)^{|R|-|T|}h_T\nonumber \end{align}

注意在这里由于 S 是全集，因此还有限制 R \sube S，同时把 (-1)^{|R|-|T|} 变成 (-1)^{|R|+|T|}，可以调换求和顺序：

f_{S} = \sum _{R \sube S \land R \not = \varnothing}(-1)^{|R|}h_R\sum_{T \sube R \land T \not = \varnothing}(-1)^{|T|}

使用二项式定理推论，由于 R \not= \varnothing，有

\sum_{T \sube R \land T \not = \varnothing}(-1)^{|T|} = -1

这样式子就变成

f_{S} = \sum _{R \sube S \land R \not = \varnothing}(-1)^{|R|+1}h_R

把 h_R 换回 f_{S-R}，得到

f_{S} = \sum _{R \sube S \land R \not = \varnothing}(-1)^{|R|+1}f_{S-R}

至此，我们说明了容斥系数为 (-1)^{|R|+1}。

那么这道题就做完了。我们可以 O(2^nn^2) 预处理出每个集合是否为独立集，再用 O(3^n) 枚举子集进行转移，总复杂度为 O(2^nn^2 + 3^n)。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 19
using namespace std;
constexpr int MOD=998244353,inv2=499122177;
inline void add(int &x,int y){x+=y,x-=x>=MOD?MOD:0;}
struct Edge{
    int u,v;
    void read(){scanf("%lld%lld",&u,&v);}
}E[N*N];
int n,m,is[1<<N],f[1<<N],pw[N];
main()
{
    scanf("%lld%lld",&n,&m),f[0]=pw[0]=1;
    for(int i=1;i<N;i++)pw[i]=(MOD-pw[i-1])%MOD;
    for(int i=1;i<=m;i++)E[i].read();
    for(int S=0;S<(1<<n);S++)
        for(int i=1;i<=m;i++)
            if((S>>E[i].u-1)&(S>>E[i].v-1)&1)is[S]=1;
    for(int S=1;S<(1<<n);S++)
        for(int T=S;T;T=(T-1)&S)
            if(!is[T])add(f[S],f[S^T]*pw[__builtin_popcountll(T)+1]%MOD);
    printf("%lld\n",f[(1<<n)-1]*m%MOD*inv2%MOD);
    return 0;
}