大致题意
做法
考虑到n的大小只有20，所以应该和状态压缩或者说集合按位表示有关。
因此，我们考虑用
F
S
F_S
FS表示考虑的点的状态为
S
S
S的情况下，所有可能的
D
A
G
DAG
DAG的方案数。
考虑每一个状态的转移，容斥一下可以得到如下转移方程：
F
S
=
∑
T
⊂
S
(
−
1
)
∣
S
−
T
∣
F
T
2
∣
E
T
,
S
−
T
∣
F_S=\sum_{T \subset S}(-1)^{|S-T|}F_T2^{|E_{T,S-T}|}
FS=T⊂S∑(−1)∣S−T∣FT2∣ET,S−T∣ 其中
E
S
,
T
E_{S,T}
ES,T表示
S
S
S和
T
T
T之间的边。
考虑到
E
T
,
S
−
T
=
E
S
−
E
T
−
E
S
−
T
E_{T,S-T}=E_S-E_T-E_{S-T}
ET,S−T=ES−ET−ES−T，我们在等式两边同时除以
E
S
E_S
ES，可以有：
F
S
2
∣
E
S
∣
=
∑
T
⊂
S
(
−
1
)
∣
S
−
T
∣
1
2
∣
E
S
−
T
∣
∗
F
T
2
∣
E
T
∣
\frac{F_S}{2^{|E_S|}}=\sum_{T \subset S}(-1)^{|S-T|}\frac{1}{2^{|E_{S-T}|}}*\frac{F_T}{2^{|E_T|}}
2∣ES∣FS=T⊂S∑(−1)∣S−T∣2∣ES−T∣1∗2∣ET∣FT 很开心的发现，这已经变成了一个子集卷积的形式，于是我们就可以用FMT或者FWT去快速计算了。
具体来说，考虑用二进制的形式表示集合，我们令
g
[
i
]
[
m
a
s
k
i
]
=
(
−
1
)
i
2
−
t
g[i][mask_i]=(-1)^{i}2^{-t}
g[i][maski]=(−1)i2−t，
f
[
i
]
[
m
a
s
k
i
]
=
F
m
a
s
k
i
∗
2
−
t
f[i][mask_i]=F_{mask_i}*2^{-t}
f[i][maski]=Fmaski∗2−t，其中
t
t
t表示
m
a
s
k
i
mask_i
maski内部的连边条数。总的转移方程可以写成：
f
[
i
]
[
m
a
s
k
i
]
=
∑
j
=
1
,
m
a
s
k
j
⊂
m
a
s
k
i
i
f
[
j
]
[
m
a
s
k
j
]
∗
g
[
i
−
j
]
[
m
a
s
k
i
⊕
m
a
s
k
j
]
f[i][mask_i]=\sum_{j=1,mask_j\subset mask_i}^{i}f[j][mask_j]*g[i-j][mask_i\oplus mask_j]
f[i][maski]=j=1,maskj⊂maski∑if[j][maskj]∗g[i−j][maski⊕maskj] 直接FWT即可，时间复杂度
O
(
n
2
2
n
)
O(n^22^n)
O(n22n)
代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define LL long long
#define pb push_back
#define INF 0x3f3f3f3f
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std
;
const int N
=25;
const int M
=1048580;
const int mod
=998244353;
const int inv2
= (mod
+ 1) / 2;
int n
,m
,cnt
[M
],tot
[M
],bin
[N
*N
],inv
[N
*N
],f
[N
][M
],g
[N
][M
],ma
[N
];
int lg(int x
) {return std
::lower_bound(bin
,bin
+n
,x
)-bin
;}
int qpow(int x
,int y
)
{
int ans
=1;
while (y
)
{
if (y
&1) ans
=(LL
)ans
*x
%mod
;
x
=(LL
)x
*x
%mod
;y
>>=1;
}
return ans
;
}
void FWT_xor(int *a
,int opt
)
{
for(int i
=1;i
<bin
[n
];i
<<=1)
for(int p
=i
<<1,j
=0;j
<bin
[n
];j
+=p
)
for(int k
=0;k
<i
;++k
)
{
int X
=a
[j
+k
],Y
=a
[i
+j
+k
];
a
[j
+k
]=(X
+Y
)%mod
;a
[i
+j
+k
]=(X
+mod
-Y
)%mod
;
if(opt
==-1)a
[j
+k
]=1ll*a
[j
+k
]*inv2
%mod
,a
[i
+j
+k
]=1ll*a
[i
+j
+k
]*inv2
%mod
;
}
}
int main()
{
scc(n
,m
);
bin
[0]=inv
[0]=1;
for (int i
=1;i
<=max(n
,m
);i
++) bin
[i
]=bin
[i
-1]*2%mod
,inv
[i
]=qpow(bin
[i
],mod
-2);
for (int i
=1;i
<=m
;i
++)
{
int x
,y
;scc(x
,y
);
ma
[x
]|=bin
[y
-1];ma
[y
]|=bin
[x
-1];
}
for (int i
=1;i
<bin
[n
];i
++) cnt
[i
]=cnt
[i
-(i
&(-i
))]+1,tot
[i
]=tot
[i
-(i
&(-i
))]+cnt
[ma
[lg(i
&(-i
))+1]&i
];
for (int i
=0;i
<bin
[n
];i
++) g
[cnt
[i
]][i
]=(cnt
[i
]&1)?inv
[tot
[i
]]:mod
-inv
[tot
[i
]];
for (int i
=0;i
<=n
;i
++) FWT_xor(g
[i
],1);
f
[0][0]=1;
FWT_xor(f
[0],1);
for (int i
=0;i
<=n
;i
++)
{
for (int j
=1;j
<=n
-i
;j
++)
for (int k
=0;k
<bin
[n
];k
++)
(f
[i
+j
][k
]+=(LL
)f
[i
][k
]*g
[j
][k
]%mod
)%=mod
;
}
FWT_xor(f
[n
],-1);
printf("%d\n",(LL
)f
[n
][bin
[n
]-1]*qpow(2*qpow(3,mod
-2),m
)%mod
);
return 0;
}
