題解

感覺極其神奇的狀壓dp

\(dp[i][S]\)表示答案為i，然后不可選的點集為S
我們每次往答案里加一個點，然后方案數是，設原來可以選的點數是y，新加入一個點后導致了除了新加的點之外x個點不能選，那么方案就是把x個數在y - 1（由于空余位置的第一個要放我們選的那個點）個位置里任意排列，方案數是\(A^{y - 1}_{x}\)

復雜度是\(O(n^2 2^n)\)但是由于我們及時的break掉它跑的飛快= =

代碼

#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <queue> #include <cmath> #define enter putchar('\n') #define space putchar(' ') #define mp make_pair #define pb push_back #define fi first #define se second #define pii pair<int,int> #define eps 1e-7 #define MAXN 3005 //#define ivorysi using namespace std; typedef long long int64; typedef double db; template<class T> void read(T &res) {res = 0;char c = getchar();T f = 1;while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {res = res * 10 + c - '0';c = getchar();}res *= f; } template<class T> void out(T x) {if(x < 0) {putchar('-');x = -x;}if(x >= 10) {out(x / 10);}putchar('0' + x % 10); }const int MOD = 998244353;int N,M; int fac[25],invfac[25],inv[25]; int AD[25],dp[25][(1 << 20) + 5],cnt[(1 << 20) + 5],A[25][25]; bool vis[(1 << 20) + 5]; int lowbit(int x) {return x & (-x); } int mul(int a,int b) {return 1LL * a * b % MOD; } int inc(int a,int b) {return a + b >= MOD ? a + b - MOD : a + b; } void Init() {inv[1] = 1;for(int i = 2 ; i <= 20 ; ++i) inv[i] = mul(inv[MOD % i],MOD - MOD / i);invfac[0] = fac[0] = 1;for(int i = 1 ; i <= 20 ; ++i) fac[i] = mul(fac[i - 1],i),invfac[i] = mul(invfac[i - 1],inv[i]);read(N);read(M);int u,v;for(int i = 1 ; i <= M ; ++i) {read(u);read(v);AD[u] |= 1 << v - 1;AD[v] |= 1 << u - 1;}for(int i = 1 ; i <= N ; ++i) AD[i] |= 1 << i - 1;for(int i = 1 ; i < (1 << N) ; ++i) cnt[i] = cnt[i - lowbit(i)] + 1; } void Solve() {vis[0] = 1;int c = 0;for(int i = 1 ; i < (1 << N) ; ++i) {for(int j = 1 ; j <= N ; ++j) {if(i >> (j - 1) & 1) {if(!(AD[j] & (i ^ (1 << j - 1)))) {vis[i] |= vis[i ^ (1 << j - 1)];}break;}}if(vis[i]) c = max(c,cnt[i]);}for(int i = 0 ; i <= N ; ++i) {for(int j = 0 ; j <= i ; ++j) {A[i][j] = mul(fac[i],invfac[i - j]);}}dp[0][0] = 1;for(int i = 0 ; i < N ; ++i) {for(int S = 0 ; S < (1 << N) ; ++S) {if(!dp[i][S]) continue;for(int j = 1 ; j <= N ; ++j) {if((1 << j - 1) & S) continue;dp[i + 1][S | AD[j]] = inc(dp[i + 1][S | AD[j]],mul(dp[i][S],A[N - cnt[S] - 1][cnt[S | AD[j]] - cnt[S] - 1]));}}}int ans = 0;for(int S = 0 ; S < (1 << N) ; ++S) {ans = inc(ans,dp[c][S]);}out(mul(ans,invfac[N]));enter; } int main() { #ifdef ivorysifreopen("f1.in","r",stdin); #endifInit();Solve(); }

轉載于:https://www.cnblogs.com/ivorysi/p/9217425.html

總結

以上是生活随笔為你收集整理的【LOJ】 #2540. 「PKUWC2018」随机算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。