本文共 2705 字，大约阅读时间需要 9 分钟。

在一个n×m的格子图中，每个白格子可以被染成蓝色或红色。多米诺骨牌可以覆盖两个连续的红色格子（水平）或两个连续的蓝色格子（垂直）。我们需要计算所有染色方案下，贡献最多多米诺骨牌的数量的总和，并对998244353取模。

解决方法

代码实现

#include 
   
    
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int N = 3e5 + 10;
ll qpow(ll x, ll n) {
    ll res = 1;
    while (n) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}
ll inv(ll x) {
    return qpow(x, mod - 2);
}
ll po[N];
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    string mp[n];
    for (int i = 0; i < n; ++i) {
        cin >> mp[i];
    }
    ll white = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (mp[i][j] == '*') continue;
            white++;
        }
    }
    int len = max(n, m) + 3;
    ll nwres = 0;
    for (int i = 2; i <= len; ++i) {
        if (i % 2 == 0) {
            nwres = (nwres + inv(qpow(2, i))) % mod;
        } else {
            nwres = (nwres - inv(qpow(2, i)) + mod) % mod;
        }
        po[i] = nwres;
    }
    ll total = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (mp[i][j] == '*') continue;
            ll cnt = 0;
            for (int k = 0; k < 2; ++k) {
                if (k == 0 && j + 1 >= m) continue;
                if (k == 1 && i + 1 >= n) continue;
                if (mp[i + k][j] == '*') cnt = 0;
                else cnt++;
            }
            if (cnt > 0) {
                total = (total + po[cnt]) % mod;
            }
        }
    }
    for (int j = 0; j < m; ++j) {
        for (int i = 0; i < n; ++i) {
            if (mp[i][j] == '*') continue;
            ll cnt = 0;
            for (int k = 0; k < 2; ++k) {
                if (k == 0 && i + 1 >= n) continue;
                if (k == 1 && j + 1 >= m) continue;
                if (mp[i + k][j] == '*') cnt = 0;
                else cnt++;
            }
            if (cnt > 0) {
                total = (total + po[cnt]) % mod;
            }
        }
    }
    ll half = inv(2);
    ll power = qpow(2, white, mod);
    total = total * half % mod;
    total = total * power % mod;
    cout << total << endl;
}
   

代码解释

通过上述步骤，我们可以高效地解决问题，并得到正确的结果。