bzoj 2669 [cqoi2012]局部极小值

3 2

X.

..

.X

60

题解

f[i][j]表示填到数i，局部最小值的填写状态为j。

i数可以填写到的位置可以分成两种，‘x’位置，和非’x’位置。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m, tot, ans, vis[30][30], p[30][2], num[1 << 9], f[30][1 << 9];
char s[30][30];
const int mod = 12345678;
int dir[8][2] = {{1, 0}, {1, -1}, {1, 1}, {0, 1}, {0, -1}, {-1, 0}, {-1, 1}, {-1, -1}};
bool check(int x, int y) { if (x <= n && x >= 1 && y <= m && y >= 1) return 1; return 0; }
int solve() {
tot = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (s[i][j] == 'X')
p[++tot][0] = i, p[tot][1] = j;
for (int i = 0; i < (1 << tot); ++i) {
memset(vis, 0, sizeof vis);
for (int j = 1; j <= tot; ++j)
//          if (i & (1 << j - 1)) {
if (!((i >> (j - 1)) & 1)) {
vis[p[j][0]][p[j][1]] = 1;
for (int k = 0; k < 8; ++k)
if (check(p[j][0] + dir[k][0], p[j][1] + dir[k][1]))
vis[p[j][0] + dir[k][0]][p[j][1] + dir[k][1]] = 1;
}
int ans = 0;
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= m; ++k)
if (vis[j][k]) ans++;
num[i] = n * m - ans;
}
memset(f, 0, sizeof f);
f[0][0] = 1;
for (int i = 1; i <= n * m; ++i)
for (int j = 0; j < (1 << tot); ++j) {
(f[i][j] += f[i - 1][j] * max(num[j] - i + 1, 0) % mod) %= mod;
for (int k = 1; k <= tot; ++k)
if (j & (1 << k - 1))
(f[i][j] += f[i - 1][j ^ (1 << k - 1)]) %= mod;
}
return f[n * m][(1 << tot) - 1];
}
void dfs(int x, int y, int k) {
if (y > m) {
dfs(x + 1, 1, k); return;
}
if (x > n) {
if (k & 1) ans = (ans - solve() + mod) % mod;
else ans = (ans + solve()) % mod;
return;
}
dfs(x, y + 1, k);
int f = 1;
for (int i = 0; i < 8; ++i)
if (s[x + dir[i][0]][y + dir[i][1]] == 'X') {
f = 0; break;
}
if (f && s[x][y] != 'X')
s[x][y] = 'X', dfs(x, y + 1, k + 1), s[x][y] = '.';
}
main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%s", s[i] + 1);
for (int j = 1; j <= m; ++j)
if (s[i][j] == 'X')
p[++tot][0] = i, p[tot][1] = j;
}
dfs(1, 1, 0);
printf("%d\n", (ans % mod + mod) % mod);
}