正題
題目連結:https://www.luogu.com.cn/problem/P6846
題目大意
給出\(n\)個點\(m\)條邊的一張有向圖，保證兩個點之間最多隻有一條邊。現在你可以取反一些邊使得圖變為一張\(DAG\)，求所有方案的取反的邊數和。
\(1\leq n\leq 18\)
解題思路
考慮到對于一種方案取反所有邊就是另一種方案，是以每種方案的取反邊數的平均值肯定是\(\frac{m}{2}\)，是以我們隻需要統計方案數就好了。
然後再考慮\(dp\)，樸素的做法是\(O(3^n)\)的，記\(G_S\)表示集合\(S\)是否是獨立集那麼有
\[F_S=\sum_{T\sube S}(-1)^{|T|+1}F_{S-T}G_T
\]
然後化成集合幂級數的形式就是
\[F=FG+1\Rightarrow F=\frac{1}{1-G}
至于集合幂級數怎麼求逆，定義占位多項式
\[G'_{S,i}=\sum_{S=0}^n[count(S)=i]G_S
然後對于每個\(G_S\)視為一個多項式求逆。
然後求逆可以用\(O(n^2)\)的反正\(n\)很小。
對于\(a\)求逆，首先有\(a^{-1}[x_0]=\frac{1}{a[x_0]}\)，然後有
\[\sum_{i=0}^na[x^i]a^{-1}[x^{n-i}]=0\Rightarrow a^{-1}[x^n]=\frac{\sum_{i=0}^{n-1}a^{-1}[x^i]a[x^{n-i}]}{a[x^0]}
這樣就可以\(O(n^2)\)遞推了。
時間複雜度：\(O(2^nn^2)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=18,P=998244353;
ll n,m,MS,c[1<<N],g[1<<N],F[N+1][1<<N],G[N+1],H[1<<N];
void FWT(ll *f,ll op){
for(ll p=2;p<=MS;p<<=1)
for(ll k=0,len=p>>1;k<MS;k+=p)
for(ll i=k;i<k+len;i++)
(f[i+len]+=f[i]*op+P)%=P;
return;
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(ll i=1,x,y;i<=m;i++){
scanf("%lld%lld",&x,&y);
x--;y--;g[(1<<x)|(1<<y)]=1;
}
MS=(1<<n);
for(ll i=0;i<n;i++)
for(ll s=0;s<MS;s++)
if(!((s>>i)&1))g[s^(1<<i)]|=g[s];
for(ll i=1;i<MS;i++){
c[i]=c[i-(i&-i)]+1;
if(!g[i])F[c[i]][i]=(c[i]&1)?1:(P-1);
}
F[0][0]=1;
for(ll i=0;i<=n;i++)FWT(F[i],1);
for(ll s=0;s<MS;s++){
for(ll i=0;i<=n;i++)F[i][s]=P-F[i][s];
G[0]=1;
for(ll i=1;i<=n;i++){
G[i]=0;
for(ll j=1;j<=i;j++)
(G[i]+=P-G[i-j]*F[j][s]%P)%=P;
}
H[s]=G[n];
// printf("%lld ",G[n]);
}
FWT(H,-1);
printf("%lld\n",(P+1)/2*H[MS-1]%P*m%P);
return 0;
}