LOJ2540 [PKUWC2018] 随机算法【状压DP】

题目分析：

听说这题考场上能被$ O(4^n) $的暴力水过，难不成出题人是毕姥爷？

首先思考一个显而易见的$ O(n^2*2^n) $的暴力DP。一般的DP都是考虑最近的加入了哪个点，然后删除后递归进行状压DP。由于这道题的题目询问方式是反过来的，处理方式也反过来。

令$ f[n][S] $表示当前有$ S $这些点，期望这些点能够构成独立集大小为$ n $。正向的考虑选择了哪个点，并把与这个点有连边的所有点在集合内进行删除，令找到的新状态为$ f[n-1][P] $。我们把$ P $中的结点与$ S $中不在$ P $中的点进行标号拼接。写成语言就是$ f[n][S]+=f[n-1][P] * \binom{|S|-1}{|P|} * |P|! $ 由于对于$ S $的每一个点都需要转移一遍，时间复杂度就变成了$ O(n^2*2^n) $。虽然跑得不快，但是由于冗余状态较多，考场上一定比例的人使用这个算法通过了这个题。

现在来考虑把它优化到$ O(n*2^n) $。由于题目期望着你获得一个最大独立集，所以我们可以发现第一维是没有必要的。因为对于一个目标状态$ S $，我们如果知道$ S $对应的最大独立集的大小的话，那么我们必定是奔着这个大小而去的。现在我们用$ g[S] $来表示$ S $对应的最大独立集大小，那么这是一个普及组题目，枚举选点然后求max就行了。再对于$ f[S] $,求$ S $对应的最大独立集大小。首先记录$ g[S] $，然后找删除某个点后的集合变为了$ g[S]-1 $的就是我们想要的转移方案，同样采用带标号的拼接。因为我们没有了第一维的负担，所以时间复杂度骤降为了$ O(n*2^n) $.

ps：我终于会用letax数学公式啦。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 const int mod = ;

 int n,m;

 int connect[maxn];

 int f[(<<)+],g[(<<)+],sz[(<<)+];

 int arr[(<<)+],C[maxn][maxn],fac[];

 int fast_pow(int now,int pw){

     if(pw == ) return now;

     int z = fast_pow(now,pw/);

     z = (1ll*z*z) % mod;

     if(pw & ) z = (1ll*z*now)%mod;

     return z;

 }

 void read(){

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;i++){

     int u,v; scanf("%d%d",&u,&v);

     connect[u] |= (<<v-);

     connect[v] |= (<<u-);

     }

     for(int i=;i<=n;i++) connect[i] |= (<<i-);

 }

 void init(){

     C[][] = ;

     for(int i=;i<=n;i++){

     C[i][] = C[i][i] = ;

     for(int j=;j<i;j++) C[i][j] = (C[i-][j-]+C[i-][j])%mod;

     }

     for(int i=;i<(<<n);i++){

     for(int j=;j<n;j++) if((<<j)&i) sz[i]++;

     }

     fac[] = ;

     for(int i=;i<=n;i++) fac[i] = (1ll*fac[i-]*i)%mod;

 }

 void dfs(int now){

     arr[now] = ;

     for(int i=;i<=n;i++){

     if(!((<<i-)&now)) continue;

     int p = now - (now&connect[i]);

     if(!arr[p]) dfs(p);

     g[now] = max(g[now],g[p]+);

     }

 }

 void dfs2(int now){

     arr[now] = ;

     for(int i=;i<=n;i++){

     if(!((<<i-)&now)) continue;

     int kk = (now&connect[i]),p = now - kk;

     if(g[p] != g[now]-) continue;

     if(!arr[p]) dfs2(p);

     f[now]+=((1ll*C[sz[now]-][sz[p]]*fac[sz[kk]-])%mod)*f[p]%mod;

     f[now] %= mod;

     }

 }

 void work(){

     init();

     g[] = ; arr[] = ;

     for(int i=;i<(<<n);i++) if(!arr[i]) dfs(i);

     memset(arr,,sizeof(arr));

     f[] = ; arr[] = ;

     dfs2((<<n)-);

     int ans = f[(<<n)-];

     ans = (1ll*fast_pow(fac[n],mod-)*ans)%mod;

     printf("%d",ans);

 }

 int main(){

     read();

     work();

     return ;

 }

巴特西

LOJ2540 [PKUWC2018] 随机算法【状压DP】

最新文章

热门文章

巴特西

LOJ2540 [PKUWC2018] 随机算法 【状压DP】

最新文章

热门文章

LOJ2540 [PKUWC2018] 随机算法【状压DP】