DDOSvoid's Blog

CF 1511E Colorings and Dominoes

发表于 更新于 分类于
本文字数： 1.6k 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/problemset/problem/1511/E

简要题意：给定一个 $n\times m$ 的网格图，格子有黑色和白色两种，现在你要将每个白色格子染成红色或蓝色，对于每一种染色方案，你需要尽可能的铺上 $1\times 2$ 的骨牌，横着的骨牌必须在两个红色格子上，竖着的骨牌必须在两个蓝色格子上，现在要求所有方案的骨牌数量之和

$n\times m\le 3\times 10^5$

Solution

首先原题相当于求期望，最后再乘上 $2$ 的若干次方即可

首先根据期望，我们可以将横着的和竖着的拆开了计算

拆开之后，我们只需求横着的若干段的期望和即可，这个东西可以提前预处理

我们令 $f_i$ 表示长度为 $i$ 的期望是多少

容易得到 $f_i=\frac12f_{i-1}+\frac12(\frac12(f_{i-2}+1)+\frac12(f_{i-2+0}))=\frac12(f_{i-1}+f_{i-2}+\frac14)$

时间复杂度 $O(n\times m)$

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
#include <iostream>
#include <stack>
#include <map>
#include <vector>
#define maxn 300010
#define ll long long
using namespace std;

const int p = 998244353;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s;
}

int n, m;

char s[maxn];

vector<int> A[maxn];

ll f[maxn], ans;
int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; int sum = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> s + 1; A[i].resize(m + 1);
        for (int j = 1; j <= m; ++j) A[i][j] = s[j] == 'o', sum += A[i][j];
    } 
    ll inv2 = pow_mod(2, p - 2), inv4 = inv2 * inv2 % p;
    f[1] = 0; f[2] = inv4;
    for (int i = 3; i <= max(n, m); ++i) f[i] = (inv2 * f[i - 1] % p + inv2 * f[i - 2] + inv4) % p;
    for (int i = 1; i <= n; ++i) 
        for (int j = 1; j <= m; ++j) {
            if (!A[i][j]) continue;
            int k = j; while (k <= m && A[i][k]) ++k;
            ans = (ans + f[k - j]) % p; j = k - 1;
        }
    for (int j = 1; j <= m; ++j)
        for (int i = 1; i <= n; ++i) {
            if (!A[i][j]) continue;
            int k = i; while (k <= n && A[k][j]) ++k;
            ans = (ans + f[k - i]) % p; i = k - 1; 
        }
    cout << ans * pow_mod(2, sum) % p << "\n";
    return 0;
}