题意(51Nod 1518):

我们要对一个n\cdot m 的棋盘进行覆盖, 利用1× 22×1的多诺牌进行覆盖, 使得无法通过一条不穿过任何骨牌内部的直线,将一种覆盖方案分割成两个部分。

< 稳定的多米诺覆盖>其实和ZJOI<多米诺骨牌>是一样的, 
只不过是一个没有障碍, 一个有障碍而已.
  • 我们考虑什么样的图案能够让一条线”割”不开了, 也就是每当有线要切割行的时候总会有竖着的多米诺 | 挡住, 切割列也是一样的, 被\ -\ 挡住,那么题意转化部分就这么过了…
  1. 相邻的两列之间会有1× 2的骨牌
  2. 相邻的两行之间会有2× 1的骨牌

分析:

这道题首先我们可以考虑所有都不横跨的情况, 那么我们对于一个n\cdot m 的矩形, 可以用状压dp来求出方案数(轮廓线dp), 大体上讲一下思路: 我们考虑枚举一条轮廓线, 而这条线上方的方块已经被铺满, 即我们只需要考虑线上的填充情况

如图左上角的样子, 那么我们再枚举轮廓线的中转点, 也就是折线点(i,j)考虑如果(i-1, j)没有被填上, 那么就一定需要填上, 接着再来看(i,j-1)的点是否有填充, 那么此时我们可以考虑填或者不填的情况, 因为我们只需要保证轮廓线上方的方块都已经被填充好, 不需要考虑线上的点的考虑情况!

然后对于这题, 可以考虑容斥系数枚举一下违反了约束的行与列, 就相当于是有许多无形的线分割, 然后就相当与是将整个部分分割, 在对每一个部分求出小矩形的方案数, 分布相乘作为最后记录答案的值, 记住要带上容斥系数!

但是如果单单这样做还是会tle, 于是我们可以只枚举行的分割然后列的分割用dp求出列的所有贡献! solve(i, j) 表示i~j的对于当前行分割的方案数是多少.

dp_i=-1 \cdot \sum_{j < i} dp_j \cdot solve(j + 1, i)

Code(ZJOI):

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double db;

const LL MOD = 19901013;
const int N = 25;

int n, m, vis[N];
LL ans, dp[N], aa[2][1 << 17], v[N - 5][N - 5][N - 5][N - 5];
char s[N][N];

LL g(int x, int cnt = 0) { while(x) cnt += (x & 1), x >>= 1; return cnt;}
LL calc(int l, int r, int n, int m)
{
    LL *pre = aa[0], *now = aa[1];
    memset(pre, 0, sizeof (LL) * (1 << m));
    pre[0] = 1;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            memset(now, 0, sizeof (LL) * (1 << m));
            for(int used = 0; used < (1 << m); used ++)
            {
                if(s[i + l][j + r] == '.')
                {
                    if((used >> j & 1))
                        (now[used & ~(1 << j)] += pre[used]) %= MOD;
                    if(j && (used >> (j - 1) & 1))
                        (now[used & ~(1 << (j - 1)) & ~(1 << j)] += pre[used]) %= MOD;
                    (now[used | (1 << j)] += pre[used]) %= MOD;
                }
                else (now[used & ~(1 << j)] += pre[used]) %= MOD;
            }
            swap(now, pre);
            if(j == m - 1)
            {
                LL res = 0;
                for(int used = 0; used < (1 << m); used++) 
                    (res += pre[used]) %= MOD;
                // printf("v[%d][%d][%d][%d] = %lld\n", l, r, i, m, v[l][r][i][m]);
                v[l][r][i + 1][m] = res;
            }
        }
    }
    LL res = 0;
    for(int i = 0; i < (1 << m); i++) 
        (res += pre[i]) %= MOD;
    return res;
}
LL f(int Left, int Right)
{
    int cnt = 1; LL res = 1;
    for(int i = 0; i < n; i++)
    {
        if(vis[i])
            res = res * v[i - cnt + 1][Left - 1][cnt][Right - Left + 1] % MOD, cnt = 1;
        else cnt ++;
    }
    return res;
}
LL solve(int x)
{
    memset(vis, 0, sizeof vis);
    memset(dp, 0, sizeof dp);
    for(int i = 0; i < n - 1; ++i) if(x >> i & 1) vis[i] = 1;
    vis[n - 1] = 1;
    for(int i = 1; i <= m; i++)
    {
        dp[i] = f(1, i);
        for(int j = 1; j < i; j++)
            dp[i] = (dp[i] - f(j + 1, i) * dp[j] % MOD) % MOD;
    }
    return (dp[m] + MOD) % MOD;
}
void init()
{
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            for(int k = 1; k <= m - j; k++)
                calc(i, j, n - i, k);
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++)
        scanf("%s", s[i]);
    init();
    for(int i = 0; i < (1 << (n - 1)); i++)
    {
        if(g(i) & 1) ans = (ans - solve(i)) % MOD;
        else ans = (ans + solve(i)) % MOD;
    }
    printf("%lld\n", (ans % MOD + MOD) % MOD);
    return 0;
}

Leave a Reply