LOJ2540 PKUWC2018 随机算法状压DP

两种$DP$：

①$f_{i,j}$表示前$i$次选择，最大独立集为$j$时达到最大独立集的方案总数，转移：$a.f_{i,j}+=f_{i+1,j+2^k}$（保证$k$加入后符合条件）；$b.f_{i,j}+=f_{i+1,j} imes ext{现在可以放的不影响最大独立集的点的数量}$，这个现在可以放的不影响最大独立集的点的数量就是不可选择的点（即已经选择和与已经选择的点相邻的点）的数量$-i$

复杂度$O(2^nn^2)$而且似乎无法优化

  1 #include<bits/stdc++.h>
  2 //This code is written by Itst
  3 using namespace std;
  4 
  5 inline int read(){
  6     int a = 0;
  7     bool f = 0;
  8     char c = getchar();
  9     while(c != EOF && !isdigit(c)){
 10         if(c == '-')
 11             f = 1;
 12         c = getchar();
 13     }
 14     while(c != EOF && isdigit(c)){
 15         a = (a << 3) + (a << 1) + (c ^ '0');
 16         c = getchar();
 17     }
 18     return f ? -a : a;
 19 }
 20 
 21 const int MOD = 998244353;
 22 bool can[21][1 << 20] , edge[21][21] , choose[21];
 23 int dp[21][1 << 20] , cnt1[1 << 20] , N , M , maxN , logg2[1 << 21];
 24 
 25 inline int poww(long long a , int b){
 26     int times = 1;
 27     while(b){
 28         if(b & 1)
 29             times = times * a % MOD;
 30         a = a * a % MOD;
 31         b >>= 1;
 32     }
 33     return times;
 34 }
 35 
 36 void dfs(int now , int size){
 37     if(N - now + size <= maxN)
 38         return;
 39     if(now == N){
 40         maxN = size;
 41         return;
 42     }
 43     dfs(now + 1 , size);
 44     for(int i = 0 ; i < now ; ++i)
 45         if(choose[i] && edge[i][now])
 46             return;
 47     choose[now] = 1;
 48     dfs(now + 1 , size + 1);
 49     choose[now] = 0;
 50 }
 51 
 52 int main(){
 53 #ifndef ONLINE_JUDGE
 54     freopen("2540.in" , "r" , stdin);
 55     //freopen("2540.out" , "w" , stdout);
 56 #endif
 57     N = read();
 58     logg2[0] = -1;
 59     for(int i = 1 ; i < (1 << N) ; ++i){
 60         cnt1[i] = cnt1[i - (i & -i)] + 1;
 61         logg2[i] = logg2[i >> 1] + 1;
 62     }
 63     for(M = read() ; M ; --M){
 64         int a = read() - 1 , b = read() - 1;
 65         edge[a][b] = edge[b][a] = 1;
 66     }
 67     dfs(0 , 0);
 68     for(int i = 0 ; i < N ; ++i){
 69         can[i][0] = 1;
 70         for(int j = 1 ; j < (1 << N) ; ++j)
 71             if(!(j & (1 << i)))
 72                 if(can[i][j - (j & -j)]){
 73                     int minN = logg2[j & -j];
 74                     if(!edge[i][minN])
 75                         can[i][j] = 1;
 76                 }
 77     }
 78     for(int i = 1 ; i < (1 << N) ; ++i)
 79         if(cnt1[i] == maxN)
 80             dp[N][i] = 1;
 81     for(int i = N - 1 ; i ; --i)
 82         for(int j = 1 ; j < (1 << N) ; ++j)
 83             if(cnt1[j] <= i && cnt1[j] <= maxN){
 84                 int cnt = 0;
 85                 for(int p = ((1 << N) - 1) ^ j ; p ; p ^= p & -p){
 86                     int k = logg2[p & -p];
 87                     if(can[k][j])
 88                         dp[i][j] = (dp[i][j] + dp[i + 1][j | (1 << k)]) % MOD;
 89                     else
 90                         ++cnt;
 91                 }
 92                 dp[i][j] = (dp[i][j] + 1ll * dp[i + 1][j] * (cnt + cnt1[j] - i)) % MOD;
 93             }
 94     long long sum = 0 , ans = 1;
 95     for(int i = 0 ; i < N ; ++i)
 96         sum = (sum + dp[1][1 << i]) % MOD;
 97     for(int i = 2 ; i <= N ; ++i)
 98         ans = ans * i % MOD;
 99     cout << sum * poww(ans , MOD - 2) % MOD;
100     return 0;
101 }

View Code

②$f_{j}$表示当前已经无法选择（即已经选择和与已经选择的点相邻的点）的集合为$j$时、独立集取到最大的方案数，设$w_i$表示与$i$相邻（包括$i$）的点集，则有转移：$f_{S cup w_i}+=f_{S} imes P_{N - |S| - 1}^{|S| - |S cap w_i| - 1}$，记得要满足最大独立集大小要是最大的。

复杂度$O(2^nn)$

 1 #include<bits/stdc++.h>
 2 //This code is written by Itst
 3 using namespace std;
 4 
 5 inline int read(){
 6     int a = 0;
 7     bool f = 0;
 8     char c = getchar();
 9     while(c != EOF && !isdigit(c)){
10         if(c == '-')
11             f = 1;
12         c = getchar();
13     }
14     while(c != EOF && isdigit(c)){
15         a = (a << 3) + (a << 1) + (c ^ '0');
16         c = getchar();
17     }
18     return f ? -a : a;
19 }
20 
21 const int MOD = 998244353;
22 long long dp[1 << 21] , maxN[1 << 21] , cnt1[1 << 21] , need[21] , jc[21] = {1} , ny[21] = {1} , N , M;
23 
24 inline int poww(long long a , int b){
25     int times = 1;
26     while(b){
27         if(b & 1)
28             times = times * a % MOD;
29         a = a * a % MOD;
30         b >>= 1;
31     }
32     return times;
33 }
34 
35 int main(){
36 #ifndef ONLINE_JUDGE
37     freopen("2540.in" , "r" , stdin);
38     //freopen("2540.out" , "w" , stdout);
39 #endif
40     N = read();
41     for(int i = 1 ; i < 1 << N ; ++i)
42         cnt1[i] = cnt1[i - (i & -i)] + 1;
43     jc[1] = ny[1] = 1;
44     for(int i = 2 ; i <= N ; ++i)
45         jc[i] = jc[i - 1] * i % MOD;
46     ny[N] = poww(jc[N] , MOD - 2);
47     for(int i = N - 1 ; i > 1 ; --i)
48         ny[i] = ny[i + 1] * (i + 1) % MOD;
49     for(int i = 0 ; i < N ; ++i)
50         need[i] = 1 << i;
51     for(M = read() ; M ; --M){
52         int a = read() - 1 , b = read() - 1;
53         need[a] |= 1 << b;
54         need[b] |= 1 << a;
55     }
56     dp[0] = 1;
57     for(int i = 0 ; i + 1 < (1 << N) ; ++i)
58         for(int j = 0 ; j < N ; ++j)
59             if(!(i & (1 << j)) && maxN[i] + 1 >= maxN[i | need[j]]){
60                 if(maxN[i] + 1 > maxN[i | need[j]]){
61                     maxN[i | need[j]] = maxN[i] + 1;
62                     dp[i | need[j]] = 0;
63                 }
64                 dp[i | need[j]] = (dp[i | need[j]] + dp[i] * jc[N - cnt1[i] - 1] % MOD * ny[N - cnt1[i] - 1 - (cnt1[need[j]] - cnt1[i & need[j]] - 1)]) % MOD;
65             }
66     cout << dp[(1 << N) - 1] * ny[N] % MOD;
67     return 0;
68 }

View Code

LOJ2540 PKUWC2018 随机算法 状压DP

LOJ2540 PKUWC2018 随机算法状压DP