Enchanted Forest (UVA 13051) by haji149
Contest: 3738    RunID: 20234875    Status: Time limit exceeded    Date: Tue Oct 24 23:00:03 JST 2017


#include <bits/stdc++.h>
#define int long long
#define N 15
using namespace std;
const int INF = 1LL<<55;
const int mod = 1e4;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
typedef pair<int,int>P;
int n;
string G[N];

int mem[1<<N],used[1<<N];

int calc(int a){
  int res = 1;
  for(int i=0;i<n;i++)
    for(int j=i+1;j<n;j++)
      if((a>>i&1) && (a>>j&1) && G[i][j] == 'Y') res = (res*2)%mod;
return res;
}

int dfs(int bit){

  if((bit&-bit) == bit) return 1;
  if(used[bit]++) return mem[bit];
  
  int res = calc(bit);
  
  for(int i = (bit-1)&bit; i > 0 ;i = (i-1)&bit){
    int j = bit ^ i;
    if(i%2 == 0)continue;
    int a = dfs(i);
    int b = calc(j);
    res = (res-a*b%mod+mod)%mod;  
  }
  return mem[bit] = res;
}


signed main(){
  int Q;
  cin>>Q;
  for(int q=1;q<=Q;q++){
    cin>>n;
    for(int i=0;i<n;i++)cin>>G[i];
    memset(used,0,sizeof(used));
    int ans = dfs((1<<n)-1);
    cout<<"Case "<<q<<": "<<ans<<endl;
  }

  


  return 0;
}