Luogu P2595 [ZJOI2009]多米诺骨牌 容斥，枚举，插头dp，轮廓线dp
真的是个好（毒）题（瘤）。其中枚举的思想尤其值得借鉴。
\(40pts\)：插头\(dp\)，记录插头的同时记录每一列的连接状况，复杂度\(O(N*M*2^{n + m} )\)。
\(100pts\)：容斥\(+\)插头\(/\)轮廓线。目前要维护每两行和每两列的限制，我们把两个限制分开讨论。预处理一下每个子矩阵如果不作限制的可行方案，然后人为地进行限制分割。对于列的限制用容斥解决，对于行的限制套在里面逐行枚举做一次\(dp\)，就可以把复杂度降到可以接受的\(O(m^3*2^n)\)。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。代码有借鉴网上。并非完全原创。
\(40pts\)：
#include <bits/stdc++.h>
using 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\)：
#include <bits/stdc++.h>
using 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;
}
更多精彩
