自动搬运

查看原文

来自洛谷，原作者为

	George1123 **

搬运于2025-08-24 22:15:45，当前版本为作者最后更新于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$，剩下的点随便拆不拆。）

$\therefore f[k]=\Pi_{(i<j)\in k}(c[i][j]+1)$

$\therefore dp[k]=f[k]-\spadesuit(k)$

于是，整个状压 $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$ 题的特点。

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

谢谢大家! !