近岁屡见 “\(n\) 不逾十八/\(n\) 不逾十六”之算题，故习演其法。
P6846 [CEOI 2019] Amusement Park
设有一图，以 \(x\) 次操作化为 DAG，则亦可以 \(m-x\) 次操作尽反其向。故当计 DAG 之数，终以 \(\frac m2\) 乘之。
设 \(f_S\) 为 \(S\) 中点集并其所有 \(\{(u,v)|u,v\in S\}\) 之边所构图中 DAG 之数。状态迁变之际，当枚举图中入度为零者集 \(T\)。为免算复，须凡 \(u,v\in T\)，二者间必无连边之独立集，且令 \(T\) 实为 \(S\) 中全体入度为零者之集。
前者易为，后者实难，故当容斥。若钦定 \(T\) 中诸点皆为入度零者，则隐言 \(T\) 外犹有此辈。依容斥之理，当有 \((-1)^{|T|+1}\) 之系数。由是得状态迁变之方程。
\[f_S=\sum_{\varnothing\subset T\subseteq S,T\text{ 为独立集}}(-1)^{|T|+1}f_{S\setminus T}
\]
以 \(O(m2^n)\) 之速预判各集可否独立集，复以 \(O(3^n)\) 遍举子集而行迁变。
#include<bits/stdc++.h>
using namespace std;
const int N=18,M=155,P=998244353;
int n,m,x[M],y[M],op[N],f[1<<N],g[1<<N];
void add(int &x,int y){if((x+=y)>=P)x-=P;}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m,op[0]=P-1,f[0]=1;for(int i=1;i<=n+1;++i)op[i]=P-op[i-1];for(int i=0;i<m;++i)cin>>x[i]>>y[i],--x[i],--y[i];for(int s=0;s<(1<<n);++s)for(int i=0;i<m;++i)if((s>>x[i]&1)&&(s>>y[i]&1)){g[s]=1;break;}for(int s=1;s<(1<<n);++s)for(int t=s;t;t=(t-1)&s)if(!g[t])add(f[s],1ll*f[s^t]*op[__builtin_popcount(t)]%P);cout<<499122177ll*f[(1<<n)-1]%P*m%P<<'\n';return 0;
}