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;
}