CodeForces 1426F Numbers of Subsequences

十月 21, 2020 2676

题意简述

给你一个字符串，其中有四种字符a b c ?，? 可以任意替换成 a b c 中的一种，求所有可能的替换方案中子序列 abc 的个数之和。

解题思路

一个计数 dp。

考虑设 dp[i][0/1/2/3] 表示考虑前 i 个字符，其中有多少个（空串） a ab abc 子序列。

转移方程：

  1. 边界：dp[0][0] = 0
  2. 默认值：dp[i][j] = dp[i - 1][j] (j = 0/1/2/3)
  3. 当枚举到字母为 a 时，dp[i][1] 可以由 dp[i - 1][0] 转移过来
  4. 当枚举到字母为 b 时，dp[i][2] 可以由 dp[i - 1][1] 转移过来
  5. 当枚举到字母为 c 时，dp[i][3] 可以由 dp[i - 1][2] 转移过来
  6. 当枚举到字母为 ? 时，上述三种转移都成立，而且默认值的 dp[i - 1][j] 在转移时要乘以三（不改变原值），因为 ? 可以自由变换成 a b c，一共三种方案，都要算上

最后的答案就是 dp[n][3]。

注意到这个柿子只会用到相邻的状态，所以可以滚动数组优化一下。

代码实现

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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl;
#define forall(G,u) for (int i_ = 0, __for_siz__ = (int) G[u].size(); i_ < __for_siz__; ++i_) 
#define com(i) ((i) % 2)

using std::cin;
using std::cout;
using std::endl;

inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

/**
 *
 * 设 f[i][0/1/2/3] 表示 考虑前 i 个字符（不是填了前 i 个），
 * 有多少个字符满足“abc” 匹配了前 0/1/2/3 位
 * （即考虑的所有字符里有“（空串）”“a”“ab”“abc”）
 * 也即 考虑前 i 个字符，“abc”匹配了前 0/1/2/3 位的子序列个数
 * 
 * 
 * 转移方程：
 * f[0][0] = 1
 * 当 s[i] = 'a' 时，f[i - 1][0] -> f[i][1]
 * 当 s[i] = 'b' 时，f[i - 1][1] -> f[i][2]
 * 当 s[i] = 'c' 时，f[i - 1][2] -> f[i][3]
 * 当 s[i] = '?' 时，上述三种转移都成立
 * 并且 f[i - 1][0/1/2/3] 要乘以三，因为一个问号可以代表三种方案
 * 因为转移仅涉及到两个相邻的状态，所以可以滚动数组优化
 *  
 */

const int ha = 1e9 + 7;

int n;
std::string ss;
long long int f[2][4];

int main() {
    std::ios::sync_with_stdio(false);
    cin >> n; cin >> ss; f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        char now = ss[i - 1]; 
        (f[com(i)][0] = f[com(i - 1)][0] * (now == '?' ? 3ll : 1ll)) %= ha;
        (f[com(i)][1] = f[com(i - 1)][1] * (now == '?' ? 3ll : 1ll)) %= ha;
        (f[com(i)][2] = f[com(i - 1)][2] * (now == '?' ? 3ll : 1ll)) %= ha;
        (f[com(i)][3] = f[com(i - 1)][3] * (now == '?' ? 3ll : 1ll)) %= ha;
        if (now == 'a' || now == '?') (f[com(i)][1] += f[com(i - 1)][0]) %= ha;
        if (now == 'b' || now == '?') (f[com(i)][2] += f[com(i - 1)][1]) %= ha;
        if (now == 'c' || now == '?') (f[com(i)][3] += f[com(i - 1)][2]) %= ha;
    }
    cout << f[com(n)][3] << endl;
    return 0;
}