#include #include #include #include #include using namespace std; constexpr double eps = 1e-20; int R = 0; int C = 0; double solve(const int R, const int C, const vector> & P, const vector> & S); vector preprocess(int n_col); int get_next_status(int prev, int know, const vector & s); double calc_prob(int mask, const vector & p); int bitcount(int mask){ int counts = 0; while (mask){ if (mask & 1) ++counts; mask >>= 1; } return counts; } template void disp(const vector< vector > & mat){ for (const auto & row : mat){ for (const auto elem : row){ cout << elem << ' '; } cout << endl; } } int main() { cin >> R >> C; vector< vector > S(R, vector(C, 0)); vector< vector > P(R, vector(C, 0.0)); // read data for (auto & row : P){ for (auto & p : row){ cin >> p; p /= 100.0; } } for (auto & row : S){ for (auto & s : row) cin >> s; } // solve cout << fixed << setprecision(12); cout << solve(R, C, P, S) << endl; return 0; } double solve(const int R, const int C, const vector> & P, const vector> & S){ auto next_status = preprocess(C); double ans = 0; int limit = 1 << C; vector old_prob(1 << C, 0.0); vector new_prob(1 << C, 0.0); old_prob[0] = 1.0; for (int r = 0; r != R; ++r){ auto s = S[r]; auto p = P[r]; for (int know = 0; know != limit; ++know){ auto new_p = calc_prob(know, p); if (new_p <= eps) continue; for (int prev = 0; prev != limit; ++prev){ auto new_status = next_status[get_next_status(prev, know, s)]; new_prob[new_status] += old_prob[prev] * new_p; } } for (int status = 0; status != 1 << C; ++status){ ans += new_prob[status] * bitcount(status); } swap(old_prob, new_prob); for (auto & np : new_prob) np = 0; } return ans; } vector preprocess(int n_col){ vector next_status(1 << (2 * n_col), 0); next_status[3] = 1; for (int c = 1; c != n_col; ++c){ int tail_limit = 1 << (2 * c - 2); for (auto head : {1, 2, 3}){ int head_mask = head << (2 * c); int head_result2 = (head >= 2) ? (1 << c) : 0; int head_result_on = 1 << c; for (auto neck : {0, 1, 2, 3}){ int neck_mask = neck << (2 * c - 2); int neck_tail_limit = neck_mask + tail_limit; int neck_threshold = 1 << (c - 1); for (int neck_tail = neck_mask; neck_tail != neck_tail_limit; ++neck_tail){ int prev = next_status[neck_tail]; if (prev >= neck_threshold){ next_status[head_mask | neck_tail] = head_result2 + prev; } else if (head != 3){ next_status[head_mask | neck_tail] = prev; } else { next_status[head_mask | neck_tail] = head_result_on + next_status[neck_tail + tail_limit]; } } } } } return next_status; } double calc_prob(int mask, const vector & p){ double prob = 1.0; for (auto pi : p){ prob *= (mask & 1) ? pi : (1 - pi); mask >>= 1; } return prob; } int get_next_status(int prev, int know, const vector & s){ // prev & (1<