P6846 [CEOI 2019] Amusement Park 題解
P6846 [CEOI 2019] Amusement Park 題解
知識點
狀壓計數 DP，DAG 計數，容斥，FWT。
分析
首先，如果我們可以花 \(c\) 把原圖轉成一張 DAG，那么就會有另一種 \(m-c\) 的方案。所以答案就變成了 \(\frac{m}{2}\) 倍的無向圖定向 DAG 計數。現在考慮 DAG 計數：設 \(f_{S}\) 表示導出子圖為 \(S\) 時，DAG 的數量。
有一個最基本的思路，要把 \(S\) 分成兩部分，代表的意義是：在確定為 DAG 的第一部分中加入第二部分，生成一個新的 DAG 的方案。發現為了形成 DAG，我們第二部分必須為一個獨立集 \(T\)，即其中沒有可以通過邊相連的節點。
我們可以通過 \(O(n2^n)\) 的復雜度預處理出每個集合是否為獨立集，記為 \(p_{S}\)（這里定義如果 \(S\) 是獨立集，則 \(p_S = 1\)）。
那么現在有轉移式：（注意 \(T\subset S\) 表示 \(T\) 是 \(S\) 的真子集）
\[f_S = \sum_{T \subseteq S,T \neq \varnothing} f_{S\setminus T} [p_{T}] \\
\]
但是這是一個會重復計數的轉移式，所以我們對其進行容斥，現在推導其容斥系數：
設 \(g_T\) 表示限定了導出子圖點集 \(S\) 下，選出的第二部分恰好為 \(T\) 時的方案數，那么實際上有：
\[f_S = \sum_{T \subseteq S,T \neq \varnothing} g_{S} \\
g_T = \sum_{T\subseteq V\subseteq S} (-1)^{|V| - |T|} f_{S\setminus V} [p_{V}] \\
\]
所以我們代入：
\[\begin{aligned}
f_S &=
\sum_{T\subseteq S,T \neq \varnothing}
\sum_{T\subseteq V\subseteq S} (-1)^{|V| - |T|} f_{S\setminus V} [p_{V}] \\
f_S &=
\sum_{V\subseteq S,V \neq \varnothing} (-1)^{|V|} f_{S\setminus V} [p_{V}]
\sum_{T\subseteq V,T \neq \varnothing} (-1)^{|T|}
\\
\end{aligned}
\]
眾所周知，有二項式定理：（\(|U| = n > 0\)）
\[\begin{aligned}
& \because
(1 - 1)^{n} = \sum_{i=0}^{n} {n\choose i} (-1)^i
\Leftrightarrow
\sum_{S\subseteq U}(-1)^{|S|}
\\
& \therefore
\sum_{S\subseteq U}(-1)^{|S|} = 0\\
& \therefore
\sum_{S\subseteq U,S\neq \varnothing}(-1)^{|S|} = -1\\
\end{aligned}
\]
所以上式可以化為：
\[\begin{aligned}
f_S &=
\sum_{V\subseteq S,V \neq \varnothing} (-1)^{|V|+1} f_{S\setminus V} [p_{V}]
\\
\end{aligned}
\]
容斥系數可以在 \(O(2^n)\) 的時間復雜度內算出，總復雜度子集枚舉為 \(O(3^n + n2^n)\)，如果 FWT 則可以優化到 \(O(n^22^n)\)。
代碼
（子集枚舉。）
#define Plus_Cat "park"
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
#define tomax(a,...) ((a)=max({(a),__VA_ARGS__}))
#define tomin(a,...) ((a)=min({(a),__VA_ARGS__}))
#define EDGE(g,i,x,y) for(int i=(g).h[(x)],y=(g)[(i)].v;~i;y=(g)[(i=(g)[i].nxt)>0?i:0].v)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);return Main();}signed Main
using namespace std;
constexpr int N(18+10),M(153+10),St((1<<18)+10);
namespace IOEcat {
//Fast IO...
} using namespace IOEcat;
namespace Modular {
//Mod Int...
} using namespace Modular;
bool p[St];
int n,m,U;
int u[M],v[M],c[St],f[St];
signed main() {
#ifdef Plus_Cat
freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
I(n,m),U=(1<<n)-1,f[0]=1,c[0]=Mod-1;
FOR(i,1,m)I(u[i],v[i]),p[1<<(u[i]-1)|1<<(v[i]-1)]=1;
FOR(S,1,U)c[S]=(S&1?Mod-c[S^1]:c[S>>1]);
FOR(S,1,U)FOR(i,1,n)if((S&1<<(i-1))&&(p[S]|=p[S^1<<(i-1)]))break;
FOR(S,1,U)for(int T(S); T; T=(T-1)&S)if(!p[T])toadd(f[S],mul(c[T],f[S^T]));
O(mul(f[U],m,Inv2),'\n');
return 0;
}
浙公網安備 33010602011771號