网格填数_牛客博客

首先我们可以如果某一个 $n \times m n × m$ 的矩阵一定确定了, 那么一定可以确定整个 $h \times w h × w$ 矩阵的奇偶性所以我们只需要考虑 $n \times m n × m$ 矩阵填数情况即可

首先我们得记录当前在哪一行, 这很显然, 然后我们还得记录整个矩阵, 每一列的和的奇偶情况, 所以我们定义状态方程为 $d p [i] [j] :$ 当前在第 $i$ 行, 每一列的奇偶情况为 $j$ 先考虑一下我们需要枚举那些东西, 首先枚举当前在第 $i$ 行, 当前这行所需要填的数的奇偶性为 $j$ , 填完上一行时, 整个矩阵每一列的奇偶情况 $k$ , 注意这里的 $j$ , 是这一行, 需要填的数字的奇偶性

所以转移方程为 $d p [i] [j \oplus k] = d p [i] [j \oplus k] * d p [i - 1] [k] * s u m dp[i][j ⊕ k] = dp[i][j ⊕ k] * dp[i - 1][k] * sum$
$s u m$ 指的是我们这一行可以填的方案数

#include<bits/stdc++.h>

using namespace std;
#define int long long 
const int mod = 1e9 + 7;
int h, w, n, m, dp[15][1 << 10];
bool is_odd[55][55], is_even[55][55];
int odd[55][55], even[55][55];
char g[55][55];

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> h >> w >> n >> m;
    
    for(int i = 1; i <= h; i ++ )
        cin >> g[i] + 1;
    
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ ) odd[i][j] = even[i][j] = 1;
    for(int i = 1; i <= h; i ++ )
        for(int j = 1; j <= w; j ++ )
        {
            if(g[i][j] != '.')
            {
                int num = g[i][j] - '0';
                if(num & 1) 
                {
                    if(is_even[i % n + 1][j % m + 1]) 
                    {
                        cout << 0 << '\n';
                        return 0;
                    }
                    is_odd[i % n + 1][j % m + 1] = 1;
                }
                else
                {
                    if(is_odd[i % n + 1][j % m + 1])
                    {
                        cout << 0 << '\n';
                        return 0;
                    }
                    is_even[i % n + 1][j % m + 1] = 1;
                }
            }
            else
            {
                odd[i % n + 1][j % m + 1] *= 5, odd[i % n + 1][j % m + 1] %= mod;
                even[i % n + 1][j % m + 1] *= 4, even[i % n + 1][j % m + 1] %= mod;
            }
        }
    dp[0][0] = 1;
    for(int i = 1; i <= n; i ++ ) // 枚举每一行
        for(int j = 0; j < 1 << m; j ++ )
        {
            int sum = 1, flag = 0, tag = 0;
            for(int k = 0; k < m; k ++ )
            {
                if(j & (1 << k)) // 填奇数
                {
                    tag ^= 1; // 记录该列的奇偶性
                    sum *= odd[i][k + 1], sum %= mod;
                    if(is_even[i][k + 1])
                    {
                        flag = 1;
                        break;
                    }
                }
                else
                {
                    sum *= even[i][k + 1], sum %= mod;
                    if(is_odd[i][k + 1])
                    {
                        flag = 1;
                        break;
                    }
                }
            }
            if(flag || !tag) continue;
            for(int k = 0; k < 1 << m; k ++ )
                dp[i][k ^ j] += dp[i - 1][k] * sum % mod, dp[i][k ^ j] %= mod;
        }
    
    cout << dp[n][(1 << m) - 1] << '\n';
}