Enchanted Forest (UVA 13051) by beet1333
Contest: 3738    RunID: 20173968    Status: Accepted    Date: Sat Oct 14 14:52:42 JST 2017


#include<bits/stdc++.h>

using namespace std;

const int mod = 10000;

struct BeetAizu
{

  BeetAizu()
  {
  }


  int N;
  string S[15];
  int look[1 << 15];
  int dp[1 << 15];

  int rec(int bit)
  {
    if(~dp[bit]) return (dp[bit]);

    if(bit == 0) return (1);
    int low = 0;
    for(int i = 0; i < N; i++) {
      if((low >> i) & 1) {
        low = i;
        break;
      }
    }

    int ret = look[bit];
    for(int i = bit; i > 0; i = (i - 1) & bit) {
      if(((i ^ bit) >> low) & 1) {
        auto get = rec(i ^ bit) * look[i];
        (ret += mod - get % mod) %= mod;
      }
    }
    return (dp[bit] = ret);
  }

  void run()
  {
    cin >> N;
    for(int i = 0; i < N; i++) {
      cin >> S[i];
    }

    for(int i = 0; i < (1 << N); i++) {
      look[i] = 1;
      for(int j = 0; j < N; j++) {
        for(int k = 0; k < j; k++) {
          if((i >> j) & 1 && (i >> k) & 1) {
            if(S[j][k] == 'Y') (look[i] *= 2) %= mod;
          }
        }
      }
    }
    memset(dp, -1, sizeof(dp));
    cout << rec((1 << N) - 1) << endl;
  }
};

int main()
{
  BeetAizu beet;
  int T;
  cin >> T;
  for(int i = 1; i <= T; i++) {
    cout << "Case " << i << ": ";
    beet.run();
  }
}