Enchanted Forest (UVA 13051) by aizu_f
Contest: 3738    RunID: 20173926    Status: Wrong answer    Date: Sat Oct 14 14:47:10 JST 2017


#include <bits/stdc++.h>
#include<set>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<stdio.h>
#define INF 100000000
#include<map>
#define P pair<int, int>
#define vector V
using namespace std;

const int mod = 10000;
int n, num_edge[1 << 15], list1[20], cnt_list, ex[300], dp[1 << 15];
char str[20][20];

int main(){
	int t, i, j ,s,p,q,tst = 0;
	for(int i = 0; i < 300; i++){
		if(i == 0) ex[i] = 1;
		else ex[i] = (ex[i - 1] << 1) % mod;
	}
	scanf("%d", &t);
	while(t-- > 0){
		tst++;
		scanf("%d", &n);
		for(i = 0; i < n; i++) scanf("%s", &str[i]);
		memset(num_edge, 0, sizeof num_edge);
		for(i = 0; i < (1 << n); i++){
			cnt_list = 0;
			for(j = 0; j < n; j++){
				if(i && (1 << j)){
					list1[cnt_list++] = j;
				}
			}
			for(int jj = 0; jj < cnt_list; jj++){
				j = list1[jj];
				for(int ss = jj + 1; ss < cnt_list; ss++){
					s = list1[ss]; 
					if(str[j][s] == 'Y'){
						num_edge[i]++;
					}					
				}
			}
		}
		memset(dp, 0, sizeof(dp));
		for(i = 0; i < (1 << n); i++){
			dp[i] = ex[num_edge[i]];
			for(j = (i & (i - 1)); j > 0; j = (j - 1) & i){
				if(j + j >= i){
					dp[i] -= (dp[j] * ex[num_edge[i - j]]) % mod;
				}
			}
			dp[i] %= mod;
			if(dp[i] < 0) dp[i] += mod;
		}	
		printf("Case %d: %d\n", tst, dp[(1 << n) - 1]);
	}
	return 0;
}