题意

给定一个含有 $n \times m \quad (nm \le 3 \cdot 10^5)$ 个格子的矩形，一开始每个格子被涂上了黑色或白色，现在可以选择将每个白色格子涂成蓝色或者红色（设白色格子的数目为 $w$ ， 显然共有 $2^w$ 种涂色的方法）。接下来在涂好色的矩形中放置大小为 $1 \times 2$ 大小的多米诺骨牌，放置的位置只能是同一行相邻的两个红色格子或者同一列相邻的两个蓝色格子上，且每个格子最多只能被骨牌覆盖一次。对于每一种涂色方式都要最大化所放置骨牌的数量，问 $2*w$ 种涂色方案所能放置骨牌数量的总和为多少。

题解

对于某一个格子，当它的颜色确定时，它所能产生的贡献的方式是固定的（若为红色则只能在水平方向产生贡献，若为蓝色则只能在垂直方向产生贡献），故我们可以将水平和垂直的贡献（即红色和蓝色的贡献）分开考虑。

以水平方向的贡献为例，对于每行，显然有黑色格子间隔的两边不会相互干扰。我们考虑每一段连续的白色段，贪心放置骨牌（即依次横着摆过去，显然这样能保证放置骨牌数量最大化）设其长度为 $x$，显然当 $x < 2$ 时对答案没有贡献。设 $dp[i]$ 表示按照上述贪心策略，连续长度为 $i + 2$ 的白色段使得最后两个格子能放置多米诺骨牌的方案数。当 $i = 0$ , 即 $x = 2$ 时，$dp[0] = 1$（当且仅当两个格子都为红色时）；当 $i = 1$ , 即 $x = 3$ 时，$dp[1] = 1$ （当第一个格子为蓝色，后两个格子为红色时能产生贡献）；当 $i = 2$ , 即 $x = 4$ 时，$dp[2] = 3$ （后两个格子为红色，第二个格子为蓝色时第一个格子两种颜色都可，或者前两个格子也都为红色）……以此类推，当 $i >= 3$ 时可得如下递推关系：

即当 $x - 2$ 位置为蓝色时之前随便填的 $2^{i - 1}$ 加上 $x - 2$ 与 $x - 3$ 位置放置了骨牌的方案数 $dp[i - 2]$，相对应的最后两个对答案的总贡献为

对于每一列也是同理。将通过计算每一行每一列的贡献并相加就能得到最终的答案。

（官方题解中给出的是巧妙的利用概率期望的思路，但是不太能讲清楚所以给出了以上思路）

代码

1
#include <iostream>
2
#include <cstdio>
3
#include <vector>
4
using namespace std;
5
const long long mod = 998244353;
6
const int N = 3e5 + 7;
7
string s[N];
8
long long two[N];
9
long long dp[N];
10
long long ksm(long long a, long long k){
11
    long long res = 1, base = a;
12
    while(k){
13
        if(k & 1) res = res * base % mod;
14
        k >>= 1;
15
        base = base * base % mod;
16
    }
17
    return res;
18
}
19
int main(){
20
    ios::sync_with_stdio(false);
21
    int n, m, w = 0;
22
    cin >> n >> m;
23
    //预处理2的幂次
24
    two[0] = 1;
25
    for(int i = 1; i <= n * m; i++) two[i] = two[i - 1] * 2 % mod;
26
    //预处理dp
27
    dp[0] = dp[1] = 1;
28
    for(int i = 2; i <= max(n, m); i++){
29
        dp[i] = (two[i - 1] + dp[i - 2]) % mod;
30
    }
31
    //统计白色格子的个数
32
    for(int i = 0; i < n; i++) cin >> s[i];
33
    for(int i = 0; i < n; i++){
34
        for(int j = 0; j < m; j++){
35
            if(s[i][j] == 'o') w++;
36
        }
37
    }
38
    long long ans = 0;
39
    for(int i = 0; i < n; i++){
40
        int cnt = 0;
41
        for(int j = 0; j <= m; j++){ //这里通过遍历到m来完成最后一段的计算
42
            if(cnt >= 2) ans = (ans + two[w - cnt] * dp[cnt - 2]) % mod;
43
            if(s[i][j] == 'o') cnt++;
44
            else{
45
                cnt = 0;
46
            }
47
        }
48
    }
49
    for(int j = 0 ; j < m; j++){
50
        int cnt = 0;
51
        for(int i = 0; i <= n; i++){
52
            if(cnt >= 2) ans = (ans + two[w - cnt] * dp[cnt - 2]) % mod;
53
            if(s[i][j] == 'o') cnt++;
54
            else{
55
                cnt = 0;
56
            }
57
        }
58
    }
59
    printf("%lld\n", ans);
60
    return 0;
61
}