/* -*- coding: utf-8 -*- * * 3615.cc: No.3615 Ge Gusser - yukicoder */ #include #include using namespace std; /* constant */ const int MAX_N = 22; const int NBITS = 1 << MAX_N; const int MAX_M = 50; const int BN = 17; const int BBITS = 1 << BN; const int BMSK = BBITS - 1; /* typedef */ using ll = long long; /* global variables */ ll bs[MAX_N], bbs[NBITS]; int bnums[BBITS]; double dp0[NBITS], dp1[NBITS]; /* subroutines */ int bitnum(ll b) { return bnums[b & BMSK] + bnums[(b >> BN) & BMSK] + bnums[(b >> (BN * 2)) & BMSK]; } /* main */ int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { char s[MAX_M + 4]; scanf("%s", s); for (int j = 0; j < m; j++) if (s[j] == 'o') bs[i] |= (1LL << j); } //for (int i = 0; i < n; i++) printf(" %lld", bs[i]); putchar('\n'); for (int bits = 1, msb = 1; bits < BBITS; bits++) { if ((msb << 1) <= bits) msb <<= 1; bnums[bits] = bnums[bits ^ msb] + 1; } int nbits = 1 << n; ll mbits = 1LL << m, mmsk = mbits - 1; bbs[0] = mmsk; for (int bits = 1, msb = 1, msi = 0; bits < nbits; bits++) { if ((msb << 1) <= bits) msb <<= 1, msi++; bbs[bits] = bbs[bits ^ msb] & bs[msi]; } //for (int bits = 0; bits < nbits; bits++) printf(" %lld", bbs[bits]); //putchar('\n'); dp0[0] = 1.0; for (int bits = 0; bits < nbits; bits++) { int bn = bitnum(bits); //printf(" dp[%d] = %lf, bn=%d, %d\n", // bits, dp[bits], bn, bitnum(bbs[bits])); double dd = (bitnum(bbs[bits]) != 1) ? dp0[bits] : 0.0; for (int i = 0, bi = 1; i < n; i++, bi <<= 1) if (! (bits & bi)) { dp0[bits | bi] += dp0[bits] / (n - bn); dp1[bits | bi] += (dp1[bits] + dd) / (n - bn); } } printf("%.10lf\n", dp1[nbits - 1]); return 0; }