题解 P5933 【[清华集训2012]串珠子】

George1123 · 2020-01-20 14:54:09 · 题解

广告：blog\diamondsuit

P5933 【[清华集训2012]串珠子】

此题算法：状压 dp

看到 n\le 16 即可想到状压做法：

用 dp[k] 表示 k 这个点集的答案（联通连边方案数）。

用 f[k] 表示 k 这个点集的连边方案数。

用 \spadesuit(k) 表示 k 这个点集不连通连边方案数。

这时求 \spadesuit(k) 需要先找一个 k 中的点 p（为了确保计算 \spadesuit(k) 时拆成的 C_ki 有点，且拆分方案不会重复计算），求出 frm=C_k\{p\}。

（其中 C 为补集符号，下同。）

可推算知 \spadesuit(k)=\sum_{i\in frm} f[i]\times dp[C_ki]。

（拆出 C_ki，剩下的点随便拆不拆。）

于是，整个状压 dp 就写完了，答案为 dp[2^n-1]。

以下是代码 + 注释

#include <bits/stdc++.h>
using namespace std;
#define lng long long
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define of(i,b,a) for(int i=b;i>=a;i--)
const int N=18;
const int M=1e9+7;
int d(){int x;scanf("%d",&x);return x;}
int n,c[N][N],cnt; lng f[1<<N],dp[1<<N];
int main(){
    n=d(),cnt=(1<<n)-1;
    fo(i,1,n)fo(j,1,n) c[i][j]=d();
    fo(k,0,cnt){ f[k]=1;
        fo(i,1,n)if(k&(1<<i-1))
            fo(j,i+1,n) if(k&(1<<j-1))
                f[k]=f[k]*(c[i][j]+1)%M; //get f[]
    }
    fo(k,1,cnt){ dp[k]=f[k];
        int frm=k^(k&-k);  //p=lowbit(k)=(k&-x)
        for(int i=frm;i;i=(i-1)&frm) //枚举frm的子集i
            dp[k]=(dp[k]-f[i]*dp[k^i]%M+M)%M; //get ♠()
    }
    printf("%lld\n",dp[cnt]);
    return 0;
}

代码很短思维难度大就是状压 dp 题的特点。

写题解不易，为我点个赞吧！

谢谢大家! !