E. Colorings and Dominoes

题意：

给定一个n∗mn*m个格子的黑白图，白色可染成红色或蓝色，共有2w2^w种染色方案(w为图中白色块数)。多米诺规格为1∗21 *2，水平放置的多米诺只有放置的两个格子都是红色时才能染色，垂直放置的多米诺只有两个格子都是蓝色时才能染色，问每种染色方案最大放置多米诺数的和。

解析：

这道题可以考虑概率做法。首先对于水平或垂直放置两种，可以将连续的白色块看做一个竖条或横条，多米诺只能放置在这个横条或竖条上。其次对于全部方案我们设EE为染色方案的期望，则答案为2w∗E2^w*E。EE的值为∑pd\sum p_d，其中pdp_d为可以在dd和d+1d+1间放置一块多米诺的概率。可以找几个简单的例子找规律。

当前放置格子前无白色块时，当且仅且当当前格子和下一个格子全部染成相同颜色时可放置，概率为14\frac{1}{4}。

当前放置格子前有一个白色块时，只有前一个白色块的颜色和后两个格子颜色不同时可以放置，概率为18\frac{1}{8}

当前放置格子前有两个白色块时，用二进制表示有0011,1011,11110011,1011,1111方式染色时可以放置，概率为316\frac{3}{16}

以上几个例子求差可以得到白色块个数与概率的关系：14−18+316−....\frac{1}{4}-\frac{1}{8}+\frac{3}{16}-....

于是只需遍历图进行计算即可得到答案。

这里还有一个细节，就是概率不能用浮点数计算，需要模拟分数进行加减。

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>

using namespace std;
#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);
const int N = 3e5 + 10;
const int M = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-3;
string Map[N];
long long fastpow(long long a, long long k) {
    long long res = 1;
    while (k) {
        if (k & 1) res = res * a % mod;
        k >>= 1;
        a = a * a % mod;
    }
    return res % mod;
}
//分数模拟相加
void Plus(long long &sum, long long &two, long long now1, long long now2) {
    if (two > now2) {
        int k = two - now2;
        now1 = now1 * fastpow(2, k) % mod;
        sum = (sum + now1) % mod;
    } else {
        int k = now2 - two;
        sum = sum * fastpow(2, k) % mod;
        two = now2;
        sum = (sum + now1) % mod;
    }
}
int main() {
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    long long cnt = 0;
    for (int i = 0; i < n; i++) {
        cin >> Map[i];
        for (int j = 0; j < m; j++) {
            if (Map[i][j] == 'o') cnt++;
        }
    }
    int c = -1;
    long long sum = 0, countOfTwo = 0;
    long long now1 = 1, now2 = 2;
    //遍历水平放置
    for (int i = 0; i < n; i++) {
        now1 = 1, now2 = 2;
        c = -1;
        for (int j = 0; j < m - 1; j++) {
            if (Map[i][j] == 'o' && Map[i][j + 1] == 'o') {
                Plus(sum, countOfTwo, now1, now2);
                now1 = (now1 * 2 % mod + c + mod) % mod;
                now2++;
                c = -c;
            } else {
                now1 = 1, now2 = 2;
                c = -1;
            }
        }
    }
    //遍历垂直放置
    for (int j = 0; j < m; j++) {
        now1 = 1, now2 = 2;
        c = -1;
        for (int i = 0; i < n - 1; i++) {
            if (Map[i][j] == 'o' && Map[i + 1][j] == 'o') {
                Plus(sum, countOfTwo, now1, now2);
                now1 = (now1 * 2 % mod + c + mod) % mod;
                now2++;
                c = -c;
            } else {
                now1 = 1, now2 = 2;
                c = -1;
            }
        }
    }
    cnt -= min(cnt, countOfTwo);
    sum %= mod;
    long long out = fastpow(2, cnt) * sum % mod;
    cout << out << '\n';
    return 0;
}