TopCoder SRM 713 Div1 500 DFSCount

这题是517毒瘤思(ban)维(ti)训练里的一道，那时候不会，最近刷tc刷到突然会了QAQ

首先可以观察一下，显然已经经过的点可以无视，那么就会形成若干个联通块。

假设我们现在在点 x x x，我们接下来随机选一个点，都一定会先把那个点所在的联通块都dfs过，然后才会访问到其它与 x x x相连但是不在之前联通块的点。

如图，若现在在 1 1 1号点，其它点都未访问过，假如接下来随机到了 2 2 2或 3 3 3，就一定会先访问完 2 , 3 , 4 2,3,4 2,3,4才会访问 5 , 6 5,6 5,6。假如随机到了 5 5 5，就会先 5 , 6 5,6 5,6后 2 , 3 , 4 2,3,4 2,3,4，但整个联通块肯定是一起的。

那么会发现答案由两部分组成，每个联通块内部的访问顺序和所有联通块的访问顺序。

用状压存储接下去要访问哪些点（在我的代码中，0表示接下去要访问）以及当前在哪个点，连通性什么的就用并查集搞一搞就行了。这题好像记搜会比较好写。

#include <bits/stdc++.h>
#define ll long long
#define fr(i,x,y) for(int i=x;i<=y;i++)
#define rf(i,x,y) for(int i=x;i>=y;i--)
#define frl(i,x,y) for(int i=x;i<y;i++)
using namespace std;
const int N=15;
int a[N][N];
ll dp[1<<N][N];
int all;
int n;

template<class T> void checkmin(T &a,const T &b) { if (b<a) a=b; } 
template<class T> void checkmax(T &a,const T &b) { if (b>a) a=b; }

class DFSCount {
public:
    long long count( vector <string> G ) ;
};

int gf(int x,int f[]){
	return f[x]==x?x:f[x]=gf(f[x],f);
}

ll dfs(int mask,int x){
    int f[N],L=0,d[N];ll b[N];
    if (mask==all) return dp[all][x]=1;
    if (dp[mask][x]) return dp[mask][x];
    frl(i,0,n) f[i]=i;
    frl(i,0,n)
     frl(j,0,n)
      if (!(mask&(1<<i))&&!(mask&(1<<j))&&a[i][j]) f[gf(i,f)]=gf(j,f);
    
    int s=0;
    frl(i,0,n){
    	if (!(mask&(1<<i))&&a[x][i]) d[++L]=i;
    	b[i]=0;
    	if (gf(i,f)==i&&!(mask&(1<<i))) s++;
    }
    fr(i,1,L){
    	int neww=all,fa=gf(d[i],f);
    	frl(j,0,n)
    	 if (!(mask&(1<<j))&&gf(j,f)==fa) neww^=1<<j;
    	neww|=1<<d[i];
    	b[fa]+=dfs(neww,d[i]);
    }
    ll ans=1;
    frl(i,0,n) if (b[i]) ans*=b[i];
    fr(i,1,s) ans*=i;
    //printf("%d %d %lld\n",mask,x,ans);
    return dp[mask][x]=ans;
}

long long DFSCount::count(vector <string> G) {
    n=G.size();all=(1<<n)-1;
    frl(i,0,n) frl(j,0,n) if (G[i][j]=='Y') a[i][j]=1;
    ll ans=0;
    frl(i,0,n) ans+=dfs(1<<i,i);
    return ans;
}