传送门

真的是神仙题,看了PoPoQQQ的题解才会做的

我们首先发现一个显然的性质,$4\times 7$的矩阵是只有可能有最多8个局部极小值的,否则随便鸽巢一下就能知道一定是不合法的状况。

我们考虑状压这8个位置是否填了数,我们发现你按表格顺序填是基本送命的,所以我们考虑从$1$到$mn$填数。

所以我们设$f[i][s]$表示当前填到第$i$个数状态为$s$的时候的方案数。

我们会发现按顺序填会有很多好处,那么我们说说好处都有啥

首先对于一个未填的极小点,它的周围8个当前都不能填数,否则它就不是极小的了。

对于一个填了的极小点,你可以放心地在它周围填数,因为当前的点都是比它大的(废话)。

那么每次填数的时候,如果填到了极小点上,那么转移显然是

$$f[i][s]+=\sum_{x \in s}f[i-1][s-\{x\}]$$

那如果当前填到了非极小点上,那么我们怎么转移呢,初步yy一下大概是这样子的

$$f[i][s] += f[i-1][s] \times cnt$$

其中$cnt$表示当前能放在的非极小点的位置数

那么每次我们都要预处理一遍$cnt$吗

可以发现$cnt$是可以根据状态$s$预处理的,对于每个极小点,周围的点显然是不能填的,因为你没放在极小点上,所以极小点也是不能填的,那么一个状态$s$的$cnt$也就是整个棋盘减去上面说的那些点再减去已经填了的$i-1$个点(注意,这$i-1$个点与这上面说的不能填的点是没有交集的,这是这道题这样做的正确性的关键)

那么我们改一下方程,设$cnt_s$表示$s$状态能填多少点。方程改为

$$f[i][s]+=f[i-1][s]\times (cnt_s – i + 1)$$

但是这里还有一个细节,你现在保证了题目指定的极小点是极小点,但是你不能保证那些非极小点不是极小点,怎么办呢?你可以暴力dfs容斥它,把所有的棋盘情况dfs一遍,然后用原来的矩阵-多一个极小点的矩阵+多两个极小点的矩阵-…

代码:

#include<bits/stdc++.h> 
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 10000000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define mod 12345678
#define eps 1e-4
#define itset std::set<node>::iterator
#define lb lower_bound
#define N 500005
#define ls (k << 1)
#define rs (k << 1 | 1)
const int tx[9] = {0, -1, -1, -1, 0, 0, 1, 1, 1};
const int ty[9] = {0, -1, 0, 1, -1, 1, -1, 0, 1};
char ch[5][10];
int n, m, f[30][260], ans, map[5][10], up, cnt[260], up2;
int vis[5][10], tim;
inline void work ()
{
    int tot = 0;
    fo (i, 1, n)
        fo (j, 1, m)
            if (ch[i][j] == 'X')
                map[i][j] = ++tot;
            else
                map[i][j] = 0;
    up = (1 << tot) - 1;
    fo (s, 0, up)
    {
        ++tim;
        cnt[s] = up2;
        fo (i, 1, n)
            fo (j, 1, m)
                if (map[i][j] && !((1 << map[i][j] - 1) & s))
                {
                    --cnt[s];//未被当前状态覆盖的低点不能放
                    fo (k, 1, 8)
                    {
                        int nx = i + tx[k], ny = j + ty[k];
                        if (!nx || !ny || n < nx || m < ny) continue;
                        if (vis[nx][ny] != tim)
                        {
                            vis[nx][ny] = tim;
                            --cnt[s];//在未覆盖低点旁边的点不能放
                        }
                    }
                }
    }

    f[0][0] = 1;
    fo (s, 0, up)
        fo (i, 1, up2)
        {
            f[i][s] = 1ll * f[i - 1][s] * (cnt[s] - i + 1) % mod;
            fo (k, 1, tot)
                if (s & (1 << k - 1)) 
                    f[i][s] = (f[i][s] + f[i - 1][s ^ (1 << k - 1)]) % mod;
        }
}
inline void dfs (int x, int y, int sum)
{
    if (m < y)
    {
        dfs(x + 1, 1, sum);
        return;
    }
    if (n < x)
    {
        work();
        ans = (ans + (sum & 1 ? -1 : 1) * f[up2][up]) % mod;
        return;
    }
    if (ch[x][y] != 'X')
    {
        fo (k, 1, 8)
        {
            int nx = x + tx[k], ny = y + ty[k];
            if (!nx || !ny || n < nx || m < ny) continue;
            if (ch[nx][ny] == 'X')
            {
                dfs(x, y + 1, sum);
                return;
            }
        }
        ch[x][y] = 'X';
        dfs(x, y + 1, sum + 1);
        ch[x][y] = '.';
    }
    dfs(x, y + 1, sum);
}
int main ()
{
    scanf("%d %d", &n, &m); up2 = n * m;
    fo (i, 1, n)
        scanf("%s", ch[i] + 1);
    fo (i, 1, n)
        fo (j, 1, m)
            if (ch[i][j] == 'X')
                fo (k, 1, 8)
                {
                    int nx = i + tx[k], ny = j + ty[k];
                    if (!nx || !ny || n < nx || m < ny) continue;
                    if (ch[nx][ny] == 'X')
                    {
                        printf("0\n");
                        return 0;
                    }
                }
    dfs(1, 1, 0);
    printf("%d\n", (ans + mod) % mod);
    return 0;
}

这道题蒟蒻qhy跑了两次90分,原因是矩阵大小只开了$5\times 8$,虽然这里m是7,并且我是从下标1开始存的,但是读入的时候字符串末尾会有个万恶的回车符,然后我的字符数组就乐滋滋地爆了。所以以后不要吝啬开这种数组否则死得早。

noip成绩出来了,没机会去pkuwc了,自闭了,估计一段时间不会更blog了,作为弱校的杠把子估计还退不了役,不过我估计我这么菜离退役不远了。

分类: 文章

quhengyi11

喵(ฅ>ω<*ฅ)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *