NC19922 - 局部极小值

题意

给你一个的整数矩阵，矩阵上面数字每个正好出现一次，我们认定一个格子里面的整数都小于它相邻（八相邻）格子的整数，那么称这个格子为局部极小值，现在给你一个所有局部极小值出现的位置，问你有多少种矩阵满足

数据范围

思路

定义格子的为

假设题目给的局部极小值集合为, 非局部极小值集合为, 可知

我们定义性质表示的格子为局部极小值, 那么这个题目的答案为

不难发现，这个一个矩阵的局部极小值不能超过，然后通过搜索可以发现容斥公式右边的范围最多次

OK，经过上面的讨论，我们现在的问题就是给你一些局部极小值点，然后如何求解有多少个矩阵的局部极小值点的集合包含我们给的那些局部极小值

我们定义方程表示填充了这些整数，局部极小值的状态为的所有方案数，

那么这个方程如何转移：

• 假设当前这个数字作为非局部极小值点，那么我们要保证这个值不能填在还没填的局部极小值点附近（包含局部极小值点），因为如果填在附近的话，那么这个局部极小值点就不成立了。不难发现，可以对每个状态预处理这个非局部极小值点的可填方案

• 假设当前整个数字作为局部极小值点，那么直接转移即可

不然发现动态规划的复杂度为

那么最差的时间复杂度为

代码

/**
 *    author: andif
 *    created: 16.09.2023 15:10:09
**/
#include<bits/stdc++.h>
using namespace std;

#define de(x) cerr << #x << " = " << x << endl
#define dd(x) cerr << #x << " = " << x << " "
#define rep(i, a, b) for(int i = a; i < b; ++i)
#define per(i, a, b) for(int i = a; i > b; --i)
#define mt(a, b) memset(a, b, sizeof(a))
#define sz(a) (int)a.size()
#define fi first
#define se second
#define qc ios_base::sync_with_stdio(0);cin.tie(0)
#define eb emplace_back
#define all(a) a.begin(), a.end()
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pdd = pair<db, db>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
const db eps = 1e-9;
const int mod = 12345678;
const int N = 5;
const int M = 8;

int n, m;
vi dx{-1, -1, -1, 0, 0, 1, 1, 1, 0};
vi dy{-1, 0, 1, -1, 1, -1, 0, 1, 0};
vector<vi> is;
int ori = 0;

int DP() { // max cnt: 16334
    vector<pii> sp;
    rep(i, 1, n + 1) rep(j, 1, m + 1) {
        if (is[i][j]) sp.push_back(pair(i, j));
    }
    int c = sz(sp);
    // de(c);
    // rep(i, 0, c) dd(sp[i].fi), de(sp[i].se);
    vector<vi> f(n * m + 1, vi((1 << c), 0));
    vi can((1 << c));
    vector<vi> vis(n + 1, vi(m + 1, 0));
    rep(i, 0, (1 << c)) {
        can[i] = n * m;
        rep(j, 1, n + 1) rep(k, 1, m + 1) vis[j][k] = 0;
        rep(j, 0, c) {
            if (i & (1 << j)) continue;
            auto [x, y] = sp[j];
            rep(k, 0, 9) {
                int nx = x + dx[k], ny = y + dy[k];
                if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
                vis[nx][ny] = 1;
            }
        }
        rep(j, 1, n + 1) rep(k, 1, m + 1) can[i] -= vis[j][k];
    }
    f[0][0] = 1;
    rep(i, 1, n * m + 1) {
        rep(j, 0, (1 << c)) {
            int d = can[j] - (i - 1);
            if (d > 0) {
                f[i][j] = (f[i][j] + 1ll * f[i - 1][j] * d % mod) % mod;
            }
            rep(k, 0, c) {
                if (j & (1 << k)) {
                    f[i][j] = (f[i][j] + f[i - 1][j ^ (1 <<k)]) % mod;
                }
            }
        }
    }
    int ret = f[n * m][(1 << c) - 1];
    if ((c - ori) & 1) ret = (-ret) % mod + mod;
    return ret % mod;
}


int dfs(int x, int y) {
    int ret = 0;
    if (y == m + 1) x++, y = 1;
    if (x == n + 1) {
        ret = DP() % mod;
        return ret;
    }
    ret = dfs(x, y + 1); // 这个点不是局部极小值
    rep(i, 0, 9) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
        if (is[nx][ny]) return ret % mod;
    }
    is[x][y] = 1;
    ret = (ret + dfs(x, y + 1)) % mod;
    is[x][y] = 0;
    return ret;
}

int main() {
    cin >> n >> m;
    is.resize(n + 1, vi(m + 1, 0));
    // dd(sz(is)), de(sz(is[0]));
    vector<string> s(n);
    rep(i, 0, n) cin >> s[i];
    rep(i, 0, n) {
        rep(j, 0, m) {
            if (s[i][j] == 'X') {
                is[i + 1][j + 1] = 1;
                ori++;
            }
        }
    }
    bool ok = true;
    rep(i, 1, n + 1) rep(j, 1, m + 1) {
        if (!is[i][j]) continue;
        rep(k, 0, 8) {
            int ni = i + dx[k], nj = j + dy[k];
            if (ni < 1 || ni > n || nj < 1 || nj > m) continue;
            if (is[ni][nj]) ok = false;
        }
    }
    cout << (ok ? dfs(1, 1) : 0) << '\n';
    return 0;
}

/*
4 7
.......
.......
.......
.......

2 2
..
..
*/