public class CheeseRolling
{
int N;
int[][] winner;
long[][] cache;
int[][] chooses;
int[] nxt;
long[] fact;
boolean powerOf2(int x)
{
return (x & (x - 1)) == 0;
}
long[] f(int st)
{
if (cache[st] != null)
return cache[st];
if (powerOf2(st))
{
cache[st] = new long[N];
for (int i = 0; i < N; i++) if (st == (1 << i))
{
cache[st][i] = 1;
return cache[st];
}
}
int cnt
= Integer.
bitCount(st
) / 2; long[] ans = new long[N];
for (int i = 0; i < nxt[cnt]; i++) if ((chooses[cnt][i] & st) == chooses[cnt][i])
{
long[] A = f(chooses[cnt][i]);
long[] B = f(chooses[cnt][i] ^ st);
for (int a = 0; a < N; a++)
{
for (int b = 0; b < N; b++)
{
ans[winner[a][b]] += A[a] * B[b];
}
}
}
return cache[st] = ans;
}
int choose(int n, int k)
{
return (int) (fact[n] / fact[k] / fact[n-k]);
}
public long[] waysToWin
(String[] wins
) {
N = wins.length;
fact = new long[N+1];
fact[0] = 1;
for (int i = 1; i <= N; i++)
fact[i] = fact[i-1] * i;
nxt = new int[N+1];
chooses = new int[N+1][];
for (int i = 0; i <= N; i++)
chooses[i] = new int[choose(N, i)];
winner = new int[N][N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
winner[i][j] = wins[i].charAt(j) == 'Y' ? i : j;
cache = new long[1 << N][];
for (int i = 0; i < (1 << N); i++)
{
chooses[cnt][nxt[cnt]++] = i;
}
return f((1 << N) - 1);
}
}