[状压DP] LOJ#2540. 「PKUWC 2018」随机算法

这题思路比较好。\(3\) 进制状压很显然,考虑减小状态。

我们状压中记下独立集是为了加点转移时判断是否能加,那么如果不计独立集具体的点,如何转移呢?

很简单,转移时不要一个一个点加,而是每次加点时,把与它相连的那些一定不在独立集中的点提前拿掉。

那些一定不会被加入独立集的点就随便放到后面就好了。

这样就可做了,设 \(f(i,S)\) 表示独立集大小为 \(i\) ,已经考虑的状态为 \(S\) , \[ f(i+1,S\cup b_k) \leftarrow f(i,S) \times A(n-|S|-1,|b_k-S\cap b_k |-1) \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int P=998244353;
int n,m,b[25],f[22][(1<<20)+5],cnt[(1<<20)+5];
int fac[25],inv[25],fac_inv[25];
int A(int n,int m){
return (LL)fac[n]*fac_inv[n-m]%P;
}
int main(){
fac[0]=1; for(int i=1;i<=21;i++) fac[i]=(LL)fac[i-1]*i%P;
inv[1]=1; for(int i=2;i<=21;i++) inv[i]=(LL)(P-P/i)*inv[P%i]%P;
fac_inv[0]=1; for(int i=1;i<=21;i++) fac_inv[i]=(LL)fac_inv[i-1]*inv[i]%P;
scanf("%d%d",&n,&m);
for(int i=0;i<=n-1;i++) b[i]=1<<i;
for(int i=1;i<=m;i++){
int x,y; scanf("%d%d",&x,&y); x--; y--;
b[x]|=1<<y; b[y]|=1<<x;
}
for(int i=1;i<=(1<<n)-1;i++)
for(int j=0;j<=n-1;j++) if((i>>j)&1) cnt[i]++;
f[0][0]=1;
for(int i=0;i<=n-1;i++)
for(int s=0;s<=(1<<n)-1;s++)
if(f[i][s]){
for(int j=0;j<=n-1;j++)
if(!((s>>j)&1)) (f[i+1][s|b[j]]+=(LL)f[i][s]*A(n-cnt[s]-1,cnt[b[j]-(b[j]&s)]-1)%P)%=P;
}
for(int i=n;i>=1;i--)
if(f[i][(1<<n)-1]){
printf("%d\n",(LL)f[i][(1<<n)-1]*fac_inv[n]%P);
return 0;
}
return 0;
}