bzoj 2669: [cqoi2012]局部极小值

题意：

有一个$n$行$m$列的整数矩阵，其中$1$到$nm$之间的每个整数恰好出现一次。如果一个格子比所有相邻格子（相邻是指有公共边或公共顶点）都小，我们说这个格子是局部极小值。
给出所有局部极小值的位置，你的任务是判断有多少个可能的矩阵。

题解：

如果我们从小到大把数填进去，局部极小值就是要满足先填它然后再填它周围的格子。因为$n, m$都很小，可以发现最多只有$8$个X，所以可以状压DP一下，$f_{i, S}$表示填了前$i$个数，$S$中的局部极小值格子已经填了的方案数。但是这样我们最后得到的方案中包含了某些其他格子作为局部极小值的方案，而题意要求是只有给出的格子是局部极小值，所以我们要把不合法的方案容斥掉。因为$n, m$很小，所以我们可以直接dfs，搜索所有可能的局部极小值的位置的组合，每一个都求一下就好了。复杂度$O($跑得飞快$)$。

代码：

#include <bits/stdc++.h>
using namespace std;

const int mod = 12345678;
int n, m, nm, px[8] = {-1, 0, 1, 1, 1, 0, -1, -1}, py[8] = {1, 1, 1, 0, -1, -1, -1, 0}, ans = 0, g[300];
char mp[5][10];
long long f[30][300];
struct th
{
    int x, y;
};

long long dp()
{/*
    for (int i = 1; i <= n; i++)
    {
        puts(mp[i] + 1);
    }
    puts("");*/
    th a[10];
    int num = 0;
    static int v[5][10], tim = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (mp[i][j] == 'X')
                a[num++] = {i, j};
    for (int i = 0; i < (1 << num); i++)
    {
        tim++;
        for (int j = 0; j < num; j++)
        {
            v[a[j].x][a[j].y] = tim;
            if (!(i & (1 << j)))
            {
                for (int k = 0; k < 8; k++)
                {
                    int x = a[j].x + px[k], y = a[j].y + py[k];
                    v[x][y] = tim;
                }
            }
        }
        g[i] = 0;
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= m; k++)
                if (v[j][k] != tim)
                    g[i]++;/*
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= m; k++)
                printf("%d", v[j][k] == tim);
            puts("");
        }
        printf("%d\n", g[i]);*/
    }
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int i = 1; i <= nm; i++)
    {
        for (int j = 0; j < (1 << num); j++)
        {
            int cnt = 0;
            for (int k = 0; k < num; k++)
                cnt += ((j >> k) & 1);
            f[i][j] = max(0LL, (g[j] - (i - cnt) + 1) * f[i - 1][j] % mod);
            // printf("g[%d] = %d cnt = %d\n", j, g[j], cnt);
            for (int k = 0; k < num; k++)
                if (j & (1 << k))
                    (f[i][j] += f[i - 1][j ^ (1 << k)]) %= mod;
            // printf("f[%d][%d] = %d\n", i, j, f[i][j]);
        }
    }
    return f[nm][(1 << num) - 1];
}
void dfs(int x, int y, int t)
{
    if (x == n + 1)
    {
        (ans += t * dp()) %= mod;
        return;
    }
    int xx = x, yy = y + 1;
    if (yy > m) xx = x + 1, yy = 1;
    dfs(xx, yy, t);
    if (mp[x][y] == '.')
    {
        bool tf = 0;
        for (int i = 0; i < 8; i++)
        {
            int xx = x + px[i], yy = y + py[i];
            if (xx > 0 && xx <= n && yy > 0 && yy <= m && mp[xx][yy] == 'X')
            {
                tf = 1;
                break;
            }
        }
        if (!tf)
        {
            mp[x][y] = 'X';
            dfs(xx, yy, -t);
            mp[x][y] = '.';
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    nm = n * m;
    for (int i = 1; i <= n; i++)
        scanf("%s", mp[i] + 1);
    dfs(1, 1, 1);
    printf("%d\n", (ans + mod) % mod);
}