两种$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} \times \text{现在可以放的不影响最大独立集的点的数量}$，这个现在可以放的不影响最大独立集的点的数量就是不可选择的点（即已经选择和与已经选择的点相邻的点）的数量$-i$
复杂度$O(2^nn^2)$而且似乎无法优化
1 #include2 //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 }
②$f_{j}$表示当前已经无法选择（即已经选择和与已经选择的点相邻的点）的集合为$j$时、独立集取到最大的方案数，设$w_i$表示与$i$相邻（包括$i$）的点集，则有转移：$f_{S \cup w_i}+=f_{S} \times P_{N - |S| - 1}^{|S| - |S \cap w_i| - 1}$，记得要满足最大独立集大小要是最大的。
复杂度$O(2^nn)$
1 #include2 //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_JUDGE37 freopen("2540.in" , "r" , stdin);38 //freopen("2540.out" , "w" , stdout);39 #endif40 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 }