vectorwyx 的博客

vectorwyx 的博客

My left brain has nothing right, my right brain has nothing left.

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

posted on 2021-01-14 17:04:23 | under 题解 |

upd:修改了一处小错误,感谢@syksykCCC神仙指正

如果只是求 $n$ 个点无向连通图的个数,做法是令 $f_{i}$ 表示 $i$ 个点的无向连通图的个数, $g_{i}$ 表示 $i$ 个点的无向不连通图的个数, $tot_{i}$ 表示 $i$ 个点的无向图个数。 $tot_{i}$ 很好求。求 $g_{i}$ 我们只需要枚举点 $i$ 所在连通块的大小,即 $g_{i}=\sum_{j=1}^{i-1} C_{i-1}^{j-1}\times f_{j}\times tot_{j-i},f_{i}=tot_{i}-g_{i}$。

换到这一题上,因为点与点之间的连边的种数是不一样的,因此我们不能只枚举连通块的大小,还要枚举连通块包含哪些点。再看到 $n\le16$,自然想到使用状压 dp 求解。

令 $f_{i},g_{i},tot_{i}$ 表示 $i$ 所代表的点集的无向连通图/无向不连通图/无向图的个数,先求 $tot_{i}$,再求 $g_{i}$。

对于 $i$ 中的任两点 $p_{1},p_{2}$,有两种情况:连边( $c_{p_{1},p_{2}}$ 种选择)或不连边( $1$ 种选择),由乘法原理可得 $tot_{i}=\prod_{p_{1}\in i}\prod_{p_{2}\in i}(c_{p_{1},p_{2}+1)}$。

$g_{i}$ 的转移方程与上面那个类似,随便选一个点 $p\in i$,令 $S$= $i-\{p\}$,也就是说 $S$ 为 $i$ 去掉 $p$ 后得到的点集。然后枚举 $S$ 的非空子集 $S1$,把 $S1$ 关于 $S$ 的补集 $S2$ 并上 $\{p\}$ 的结果作为 $p$ 所在连通块的点集,即 $g_{i}=\sum_{S1\subset S,S1\not= \varnothing}tot_{i}\times f_{S2\cup\{p\}}$。最后的答案就是 $f_{2^{n}-1}$。总时间复杂度为 $O(3^{n}+2^{n}n^{2})$

代码如下(点个赞再走吧QAQ,谢谢您!):

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define lowbit(x) x&(-x)
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
#define go(i,x,y) for(int i=x;i>=y;--i)
using namespace std;
inline int read(){ int x=0,fh=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') fh=-1; ch=getchar(); } while(isdigit(ch)){ x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*fh; }

const int N=1<<16,yrz=1e9+7;
int f[N],g[N],tot[N],n,c[20][20];//f[i]:连通 g[i]:不连通 

int main(){
    cin>>n;
    fo(i,1,n) fo(j,1,n) c[i][j]=read();
    int pw=(1<<n)-1;
    fo(i,1,pw){
        int p=-1,bit[20],top=0;
        go(j,n-1,0) if(i&(1<<j)){
            p=(1<<j);
            bit[++top]=j+1;
        }
        tot[i]=1;
        fo(j,1,top)
            fo(k,j+1,top) tot[i]=1ll*tot[i]*(c[bit[j]][bit[k]]+1)%yrz;
        int S=i-p;
        for(int S1=S;S1;S1=(S1-1)&S){
            int S2=(i^S1)|p;
            g[i]=(g[i]+1ll*f[S2]*tot[S1])%yrz;
        }
        f[i]=(tot[i]+yrz-g[i])%yrz;
        //printf("%d:%d %d %d\n",i,tot[i],f[i],g[i]);
    }
    cout<<f[pw];
    return 0;
}
/*
-------------------------------------------------
*/