[LOJ 2540]「PKUWC2018」随机算法

Posted on | Edited on | In , | Views:

题目链接

LOJ 2540

前言

PKUWC d2t1，还是比较清新的。

做法

先看一眼数据范围，$n \le20$，那应该是个状压dp了。
为了方便说明，以直接覆盖来称那些我选的点，间接覆盖来称那些由于和直接覆盖的点相连，而不能选的点，被覆盖的点就是这两个点集的并。
首先先想到的自然是以$f[i],g[i]$分别表示目前被覆盖的点的状态为i时的最大独立集的大小和方案数。
先预处理选每个点会导致哪些点被间接覆盖，显然是与我直接相连的点，而我自己是直接覆盖。
考虑转移，枚举一个未被覆盖的点，更新一下f和g。
最后除以阶乘。

但是这样会有问题，以样例来说，3 1 2 与 3 2 1被当成了同一种状态，因为你并没有枚举间接覆盖点2在什么时候选。
所以我们用$f[i][j]$,$g[i][j]$来表示所有被覆盖的点集为i，被间接覆盖的点的点集为j。
但是这样复杂度显然爆了。
事实上所有被间接覆盖的点本质上都是一样的，所以我们并不需要知道是哪些，而只要知道有几个就行了。
如果一个点原先是被间接覆盖，我选他，相当于只把他这个点变成直接覆盖，而不把与他相连的点视为间接覆盖，因为事实上我并没有把它加入独立集，只不过相当于是在选择序列的最后把它加入。
用$f[i][j]$表示已经选了i个点，被覆盖的点集为j的最大独立集大小,$g[i][j]$表示方案数。
对于(i,j)统计出j中有多少个点已经被覆盖了，减去i就是被间接覆盖的点的个数了。
转移就分为取未被覆盖点还是间接覆盖点就行了。

代码

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (100005)
using namespace std;
int n,m,x,y,jc; 
int kk[N],f[21][1<<20],g[21][1<<20];
const int P=998244353;
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
int Inc(int a,int b){
    return (a+b>=P)?(a+b-P):(a+b);
}
int ksm(int a,int b){
    int ret=1;
    while (b>1){
        if (b&1) ret=1ll*ret*a%P;
        b>>=1;
        a=1ll*a*a%P;
    }
    return 1ll*ret*a%P;
}
int main(){
    read(n),read(m);
    jc=1;
    for (int i=1;i<=n;i++) kk[i]=(1<<i-1),jc=1ll*jc*i%P;
    for (int i=1;i<=m;i++){
        read(x),read(y);
        kk[x]|=(1<<y-1);
        kk[y]|=(1<<x-1);
    } 
    g[0][0]=1;
    f[0][0]=0;
    for (int i=1;i<=n;i++){
        for (int zt=0;zt<(1<<n);zt++){
            if (!g[i-1][zt]) continue;
            int tt=0;
            for (int j=1;j<=n;j++){
                if ((zt>>j-1)&1) tt++;
            }
            for (int j=1;j<=n;j++){
                if (!((zt>>j-1)&1)){
                    int tow=zt|kk[j];
                    if (f[i][tow]<f[i-1][zt]+1){
                        f[i][tow]=f[i-1][zt]+1;
                        g[i][tow]=g[i-1][zt];
                    }
                    else if (f[i][tow]==f[i-1][zt]+1){
                        g[i][tow]=Inc(g[i][tow],g[i-1][zt]);
                    }
                }
            }
            if (tt-i+1>0){
                if (f[i-1][zt]>f[i][zt]){
                    f[i][zt]=f[i-1][zt];
                    g[i][zt]=1ll*g[i-1][zt]*(tt-i+1)%P;
                } 
                else if (f[i-1][zt]==f[i][zt]){
                    g[i][zt]=Inc(g[i][zt],1ll*g[i-1][zt]*(tt-i+1)%P);
                }
            }
            
        }
        //for (int zt=0;zt<(1<<n);zt++){
    //        printf("%d %d\n",f[i][zt],g[i][zt]);
        //}
    //    puts("");
    }
    
    printf("%lld",1ll*g[n][(1<<n)-1]*ksm(jc,P-2)%P);
    return 0;
}