真的是个好（毒）题（瘤）。其中枚举的思想尤其值得借鉴。
\(40pts\)：插头\(dp\)，记录插头的同时记录每一列的连接状况，复杂度\(O(N*M*2^{n + m} )\)。
\(100pts\)：容斥\(+\)插头\(/\)轮廓线。目前要维护每两行和每两列的限制，我们把两个限制分开讨论。预处理一下每个子矩阵如果不作限制的可行方案，然后人为地进行限制分割。对于列的限制用容斥解决，对于行的限制套在里面逐行枚举做一次\(dp\)，就可以把复杂度降到可以接受的\(O(m^3*2^n)\)。
代码有借鉴网上。并非完全原创。
\(40pts\)：
#includeusing namespace std;const int N = 15 + 5;const int base = 2999830;const int Mod = 19901013;const int M = 3000000 + 5;typedef unsigned int uint;int n, m, cur, las, cnt[2], can[N][N];int nxt[M], head[M], dp[2][M]; uint Hash[2][M];int get_wei (uint zt, int wei) { return (zt >> wei) % 2;}int alt_wei (uint zt, int wei, int val) { return zt + ((0ll + val - get_wei (zt, wei)) << wei);}void update (uint zt, int val) { uint _zt = zt % base; for (int i = head[_zt]; i; i = nxt[i]) { if (Hash[cur][i] == zt) { (dp[cur][i] += val) %= Mod; return; } } nxt[++cnt[cur]] = head[_zt]; head[_zt] = cnt[cur]; Hash[cur][cnt[cur]] = zt;// cout << "dp[" << cur << "][" << cnt[cur] << "] = " << val << endl; dp[cur][cnt[cur]] = val;} int get_val (uint zt) { uint _zt = zt % base; for (int i = head[_zt]; i; i = nxt[i]) { if (Hash[cur][i] == zt) { return dp[cur][i]; } } return 0;}void change_row () { for (int i = 1; i <= cnt[cur]; ++i) { uint &zt = Hash[cur][i]; if (get_wei (zt, m + m) == 0) { dp[cur][i] = 0;//到不了下一行 } for (int i = m; i >= 1; --i) { zt = alt_wei (zt, i, get_wei (zt, i - 1)); } zt = alt_wei (zt, 0, 0); // 全都向后移一位 zt = alt_wei (zt, m + m, 0); // 到下一行的标记清空 } }int solve () { update (1 << (m + m), 1); for (int i = 1; i <= n; ++i) { change_row (); for (int j = 1; j <= m; ++j) {// cout << "i = " << i << " j = " << j << endl; las = cur, cur ^= 1, cnt[cur] = 0; memset (head, 0, sizeof (head)); for (int k = 1; k <= cnt[las]; ++k) { uint zt = Hash[las][k]; int b1 = get_wei (zt, j - 1); int b2 = get_wei (zt, j - 0); int val = dp[las][k]; if (val == 0) continue; // 不转移的小优化 // cout << "b1 = " << b1 << " b2 = " << b2 << endl; if (!can[i][j]) { if (!b1 && !b2) { update (zt, val); } } else { if (b1 == 0 && b2 == 0) { if (can[i][j + 1]) { uint _zt = zt; _zt = alt_wei (_zt, j - 0, 1); // 右插头改为 1 _zt = alt_wei (_zt, m + j, 1); // j 列和 j + 1 列相连 update (_zt, val); } if (can[i + 1][j]) { uint _zt = zt; _zt = alt_wei (_zt, j - 1, 1); // 下插头改为 1 _zt = alt_wei (_zt, m + m, 1); // 和下一行连通 update (_zt, val); } update (zt, val); // 注意你并不需要放满所有没有障碍的格子 } if (b1 + b2 == 1) { // 有一个连入的插头 uint _zt = zt; _zt = alt_wei (_zt, j - 0, 0); _zt = alt_wei (_zt, j - 1, 0); update (_zt, val); } } }// cout << "las : " << endl;// for (int k = 1; k <= cnt[las]; ++k) {// cout << "state = " << Hash[las][k] << " val = " << dp[las][k] << endl;// }// cout << "cur : " << endl;// for (int k = 1; k <= cnt[cur]; ++k) {// cout << "state = " << Hash[cur][k] << " val = " << dp[cur][k] << endl;// }// cout << endl; } } uint fin = 0; for (int i = m + 1; i < m + m; ++i) { fin |= (1 << i); } return get_val (fin);}int main () { cin >> n >> m; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { int ch = getchar (); while (ch != '.' && ch != 'x') { ch = getchar (); } if (ch == '.') { can[i][j] = true; } } }// for (int i = 1; i <= n; ++i) {// for (int j = 1; j <= m; ++j) {// cout << can[i][j] << " ";// }// cout << endl;// } cout << solve () << endl;}
\(100pts\)：
#includeusing namespace std;const int N = 15 + 5;const int M = 40000 + 5;const int Mod = 19901013;int n, m, top, ans; int f[N], num[N], tmp[2][M], dp[N][N][N][N];bool mp[N][N];int ask (int u, int v) { return (u >> v) % 2;}void work (int w, int u, int v) { int las = 0, tot = (1 << (v - u + 1)) - 1; for (int i = 0; i <= tot; ++i) { tmp[0][i] = 0; } int t2 = 0; for (int i = u; i <= v; ++i) { if (mp[w][i]) { t2 |= (1 << (i - u)); } } tmp[0][t2] = 1; for (int i = w + 1; i <= m + 1; ++i) { int zt = 0; for (int j = u, t = 0; j <= v; ++j, ++t) { zt |= (mp[i][j] << t); int cur = las ^ 1; for (int k = 0; k <= tot; ++k) tmp[cur][k] = 0; for (int k = 0; k <= tot; ++k) { if(!tmp[las][k]) continue; int t2 = k; if (ask(t2,t) != mp[i][j]) { t2 ^= (1 << t); } (tmp[cur][t2] += tmp[las][k]) %= Mod; if (ask (k, t)) continue; if (j != v && !ask (k, t + 1)) { t2 = k | (1 << (t + 1)); if (ask (t2, t) != mp[i][j]) { t2 ^= (1 << t); } (tmp[cur][t2] += tmp[las][k]) %= Mod; } if(!mp[i][j]) { t2 = k | (1 << t); (tmp[cur][t2] += tmp[las][k]) %= Mod; } } las = cur; } dp[w][u][i - 1][v] = tmp[las][zt]; }}int main () { cin >> m >> n; for(int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { int ch = getchar (); while (ch != '.' && ch != 'x') { ch = getchar (); } mp[i][j] = (ch == 'x'); } } for (int i = 1; i <= n; ++i) { for (int j = i; j <= n; ++j) { for (int k = 1; k <= m; ++k) { work (k, i, j); } } } int tot = (1 << (n - 1)) - 1; for(int i = 0; i <= tot; ++i) { int top = 1; num[top] = 0; for (int j = 0; j < n - 1; ++j) { if (ask (i, j)) num[++top] = j + 1; } num[++top] = n; for (int d = 1; d <= m; ++d) { for (int u = 1; u <= d; ++u) { int t = 1; for(int j = 2; j <= top; ++j) { int p = num[j - 1] + 1, q = num[j]; t = (1ll * t * dp[u][p][d][q]) % Mod; } if (u == 1) { f[d] = t; } else { f[d] = (0ll + f[d] - (1ll * t * f[u - 1])) % Mod; } } } (f[m] += Mod) %= Mod; if (top % 2 == 1) { (ans -= f[m]) %= Mod; } else { (ans += f[m]) %= Mod; } } cout << (ans + Mod) % Mod << endl;}