#include #include #include #include #include #include #include #include using namespace std; using uint64 = unsigned long long; #define rep(i, n) for (int i = 0; i < int(n); ++i) constexpr int ipow(int base, int e, int res = 1) { return e == 0 ? res : (e & 1) ? ipow(base * base, e / 2, res * base) : ipow(base * base, e / 2, res); } using Pair = pair; Pair operator + (const Pair& lhs, const Pair& rhs) { return Pair(lhs.first + rhs.first, lhs.second + rhs.second); } // precision ... Pair operator - (const Pair& lhs, const Pair& rhs) { return Pair(lhs.first - rhs.first, lhs.second - rhs.second); } Pair& operator += (Pair& lhs, const Pair& rhs) { return lhs = lhs + rhs; } constexpr int N = 11; constexpr int NH = (N + 1) >> 1; constexpr int three_N = ipow(3, N); double P[N][N]; int S[N][N]; Pair dp[2][1 << N]; Pair cumu[three_N]; int offsets[1 << N]; uint64 conv_s1[1 << N]; int conv_s2[2][2][1 << (3 * NH)]; template void arith_transform_plus(T* A, int lvn) { int n = 1 << lvn; reverse(A, A + n); for (int lvm = lvn; lvm > 0; --lvm) { int m = 1 << lvm; int mh = m >> 1; for (int r = 0; r < n; r += m) rep(j, mh) A[r + j] += A[r + mh + j]; } } template void sum(T* A, int lv, T* res) { int total = 1 << lv; int pos = 0; rep(i, total) { res[pos++] = A[i]; int f = i; int t = 1; while (f) { int r = f & -f; int ofs = offsets[i ^ r]; rep(j, t) res[pos + j] = res[ofs + j] - res[pos - t + j]; pos += t; t <<= 1; f ^= r; } } } int ctz(int n) { return __builtin_ctz(n); } int pop_count(int n) { return __builtin_popcount(n); } int main() { int R, C; scanf("%d %d", &R, &C); int CH = (C + 1) >> 1; int r; rep(i, R) rep(j, C) scanf("%d", &r), P[i][j] = r / 100.; rep(i, R) rep(j, C) scanf("%d", &S[i][j]), S[i][j] = 4 - S[i][j]; int total = 1 << C; // pre int ofs = 0; rep(i, total) offsets[i] = ofs, ofs += 1 << pop_count(i); rep(i, total) { uint64 f = 0; rep(x, C) if (i & (1 << x)) f |= 1ull << (3 * x); conv_s1[i] = f; } rep(h, 2) rep(c, 2) rep(i, 1 << (3 * CH)) { int points[NH]; rep(x, CH) points[x] = (i >> (3 * x)) & 7; if (c == 1) { if (h == 0) { points[CH - 1] += 1; } else { points[0] += 1; } } rep(x, CH - 1) if (points[x] >= 4) points[x + 1] += 1; rep(x, CH - 1) if (points[CH - 1 - x] >= 4) points[CH - 2 - x] += 1; int s = 0; rep(x, CH) if (points[x] >= 4) s |= 1 << x; if (c == 0) { if (h == 0) { if (points[CH - 1] >= 4) s = -s; } else { if (points[0] >= 4) s = -s; } } conv_s2[h][c][i] = s; } // dp auto* curr = dp[0], *next = dp[1]; fill(curr, curr + total, Pair(0, 0)); curr[0] = Pair(0., 1.); arith_transform_plus(curr, C); sum(curr, C, cumu); rep(y, R) { fill(next, next + total, Pair(0, 0)); rep(s2, total) { double p = 1.0; rep(x, C) p *= (s2 & (1 << x)) ? P[y][x] : 1. - P[y][x]; if (p == 0) continue; uint64 f2 = 0; rep(x, C) if (s2 & (1 << x)) f2 |= uint64(S[y][x]) << (3 * x); auto s1 = s2; int ofs = offsets[s1] + (1 << pop_count(s2)) - 1; do { if (cumu[ofs].second) { uint64 f = conv_s1[s1] + f2; int lo = f & ((1 << (3 * CH)) - 1); int hi = f >> (3 * CH); int nstate = 0; if (conv_s2[0][0][lo] < 0) { nstate = (-conv_s2[0][0][lo]) | (conv_s2[1][1][hi] << CH); } else if (conv_s2[1][0][hi] < 0) { nstate = (conv_s2[0][1][lo]) | ((-conv_s2[1][0][hi]) << CH); } else { nstate = (conv_s2[0][0][lo]) | (conv_s2[1][0][hi] << CH); } next[nstate] += Pair(p * (cumu[ofs].first + pop_count(nstate) * cumu[ofs].second), p * cumu[ofs].second); } s1 = (s1 - 1) & s2; ofs -= 1; } while (s1 != s2); } swap(curr, next); arith_transform_plus(curr, C); sum(curr, C, cumu); } printf("%.12f\n", cumu[0].first); return 0; }