\u7ed9\u5b9a\u4e00\u4e2a n\u00d7m \u7684\u77e9\u5f62\u8868\u683c\uff0c\u5176\u4e2d\u6709\u4e00\u4e9b\u4f4d\u7f6e\u6709\u969c\u788d\u3002\u73b0\u5728\u8981\u5728\u8fd9\u4e2a\u8868\u683c\u5185\u653e\u4e00\u4e9b 1\u00d72 \u6216\u8005 2\u00d71 \u7684\u591a\u7c73\u8bfa\u9aa8\u724c\uff0c\u4f7f\u5f97\u4efb\u4f55\u4e24\u4e2a\u591a\u7c73\u8bfa\u9aa8\u724c\u6ca1\u6709\u91cd\u53e0\u90e8\u5206\uff0c\u4efb\u4f55\u4e00\u4e2a\u9aa8\u724c\u4e0d\u80fd\u653e\u5230\u969c\u788d\u4e0a\u3002
\n\u5e76\u4e14\u6ee1\u8db3\u4efb\u4f55\u76f8\u90bb\u4e24\u884c\u4e4b\u95f4\u90fd\u6709\u81f3\u5c11\u4e00\u4e2a\u9aa8\u724c\u6a2a\u8de8\uff0c\u4efb\u4f55\u76f8\u90bb\u4e24\u5217\u4e4b\u95f4\u4e5f\u90fd\u81f3\u5c11\u6709\u4e00\u4e2a\u9aa8\u724c\u6a2a\u8de8\u3002\u6c42\u6709\u591a\u5c11\u79cd\u4e0d\u540c\u7684\u653e\u7f6e\u65b9\u6cd5\uff0c\u6ce8\u610f\u4f60\u5e76\u4e0d\u9700\u8981\u653e\u6ee1\u6240\u6709\u6ca1\u6709\u969c\u788d\u7684\u683c\u5b50\u3002<\/p>\n
<\/p>\n
\u56de\u5fc6\u591a\u7c73\u8bfa\u9aa8\u724c\u5b8c\u7f8e\u8986\u76d6\u3002\u3002\u663e\u7136\u6211\u4eec\u53ef\u4ee5\u8f6e\u5ed3\u7ebf DP\u3002\u3002<\/p>\n
\r\n...\r\n swap(p, q); f[p].clear();\r\n\r\n ECH(it, f[q]){\r\n d = it->se; int s = it->fi;\r\n if(j && !_1(s, j) && _1(s, j-1)) f[p][s^_1(j-1)] += d; \/\/ \u6a2a\u7740\u653e\r\n f[p][s^_1(j)] += d; \/\/ \u7ad6\u7740\u653e\u6216\u4e0d\u653e...\r\n } \r\n<\/pre>\n\u3002\u3002\u7a0d\u52a0\u4fee\u6539\u53ef\u4ee5\u652f\u6301\u969c\u788d\u4ee5\u53ca\u7a7a\u9699\u3002\u3002\u3002\u3002<\/p>\n
\r\n swap(p, q); f[p].clear();\r\n ECH(it, f[q]){\r\n d = it->se; int s = it->fi;\r\n\r\n if (buf[i1][j] != '.'){\r\n if (!_1(s, j)) f[p][s] += d; \/\/ \u6709\u969c\u788d\u3001\u5fc5\u987b\u4e0d\u653e\r\n }\r\n else{\r\n\r\n if(j != j0 && !_1(s, j) && _1(s, j-1) && buf[i1][j-1] == '.') f[p][s^_1(j-1)] += d; \/\/ \u6a2a\u7740\u653e\r\n\r\n if (!_1(s, j)){ \/\/ \u662f\u5426\u6ca1\u88ab\u8986\u76d6\r\n f[p][s] += d; \/\/ \u4e0d\u653e\r\n f[p][s^_1(j)] += d; \/\/ \u7ad6\u7740\u653e\r\n }\r\n else{ \r\n f[p][s^_1(j)] += d; \/\/ \u4e0d\u653e \r\n }\r\n }\r\n }\r\n<\/pre>\n\u3002\u3002\u3002\u56e0\u6b64\u5269\u4e0b\u53ea\u9700\u8981\u8003\u8651 solid \u7684\u95ee\u9898\u3002\u3002\u3002
\n\u3002\u65b9\u6cd5\u4e00\uff1a\u52a0\u7ef4\u3002\u3002\u590d\u6742\u5ea6\u592a\u9ad8\u3002
\n\u3002\u65b9\u6cd5\u4e8c\uff1a\u5de7\u5999\u7684\u5bb9\u65a5\u3002\u3002<\/p>\n
\r\nconst int N = 15;\r\n\r\nint n, m; char buf[N][N+1];\r\nmap<int, Int> f[2]; Int d; int p, q;\r\nInt ff[N+1][N+1][N+1][N+1], gg[N+1][N+1], g[N+1], z;\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n \/\/freopen("\/users\/xiaodao\/desktop\/Exercise\/out.txt", "w", stdout);\r\n#endif\r\n\r\n RD(n, m); REP(i, n) RS(buf[i]);\r\n REP(i0, n) REP(j0, m) FOR(j1, j0, m){\r\n\r\n REP(i, 2) f[i].clear();\r\n p = 0, q = 1; f[p][0] = 1;\r\n\r\n FOR(i1, i0, n){\r\n FOR_1(j, j0, j1){\r\n swap(p, q); f[p].clear();\r\n ECH(it, f[q]){\r\n d = it->se; int s = it->fi;\r\n\r\n if (buf[i1][j] != '.'){\r\n if (!_1(s, j)) f[p][s] += d;\r\n }\r\n else{\r\n\r\n if(j != j0 && !_1(s, j) && _1(s, j-1) && buf[i1][j-1] == '.') f[p][s^_1(j-1)] += d;\r\n\r\n if (!_1(s, j)){\r\n f[p][s] += d;\r\n f[p][s^_1(j)] += d;\r\n }\r\n else{\r\n f[p][s^_1(j)] += d;\r\n }\r\n }\r\n }\r\n }\r\n ff[i0][i1][j0][j1] = f[p][0];\r\n }\r\n }\r\n\r\n\r\n REP(s, _1(m-1)){\r\n\r\n REP(i0, n) FOR(i1, i0, n){\r\n gg[i0][i1] = 1; int p = -1, ss = s; ss |= _1(m-1);\r\n while (ss){\r\n int t = low_bit(ss);\r\n ss ^= t; t = lg2(t);\r\n gg[i0][i1] *= ff[i0][i1][p+1][t];\r\n p = t;\r\n }\r\n }\r\n\r\n REP_1(i, n){\r\n g[i] = gg[0][i-1]; REP_1(j, i-1) g[i] -= g[j] * gg[j][i-1];\r\n }\r\n if (count_bits(s) & 1) z -= g[n];\r\n else z += g[n];\r\n }\r\n cout << int(z) << endl;\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Brief description: \u7ed9\u5b9a\u4e00\u4e2a n\u00d7m \u7684\u77e9\u5f62\u8868\u683c\uff0c\u5176\u4e2d\u6709\u4e00\u4e9b\u4f4d\u7f6e\u6709\u969c\u788d\u3002\u73b0\u5728\u8981\u5728\u8fd9\u4e2a\u8868\u683c\u5185\u653e\u4e00\u4e9b 1\u00d72 \u6216\u8005 2\u00d71 \u7684\u591a\u7c73\u8bfa\u9aa8\u724c\uff0c\u4f7f\u5f97\u4efb\u4f55\u4e24\u4e2a\u591a\u7c73\u8bfa\u9aa8\u724c\u6ca1\u6709\u91cd\u53e0\u90e8\u5206\uff0c\u4efb\u4f55\u4e00\u4e2a\u9aa8\u724c\u4e0d\u80fd\u653e\u5230\u969c\u788d\u4e0a\u3002 \u5e76\u4e14\u6ee1\u8db3\u4efb\u4f55\u76f8\u90bb\u4e24\u884c\u4e4b\u95f4\u90fd\u6709\u81f3\u5c11\u4e00\u4e2a\u9aa8\u724c\u6a2a\u8de8\uff0c\u4efb\u4f55\u76f8\u90bb\u4e24\u5217\u4e4b\u95f4\u4e5f\u90fd\u81f3\u5c11\u6709\u4e00\u4e2a\u9aa8\u724c\u6a2a\u8de8\u3002\u6c42\u6709\u591a\u5c11\u79cd\u4e0d\u540c\u7684\u653e\u7f6e\u65b9\u6cd5\uff0c\u6ce8\u610f\u4f60\u5e76\u4e0d\u9700\u8981\u653e\u6ee1\u6240\u6709\u6ca1\u6709\u969c\u788d\u7684\u683c\u5b50\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[22],"tags":[116],"class_list":["post-1203","post","type-post","status-publish","format-standard","hentry","category-bzoj","tag-116"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-jp","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1203","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=1203"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1203\/revisions"}],"predecessor-version":[{"id":1204,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1203\/revisions\/1204"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1203"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1203"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1203"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}