[AtCoderABC104D] We Love ABC (DP, 计数)

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：

链接：https://abc104.contest.atcoder.jp/tasks/abc104_d

给一个只含有ABC?四种字符的字符串，?可以替换成ABC中的任意一个字符，现在要你统计所有的ABC的组合个数。

这题比赛时间内写搓了，因为误读了题目的统计结果，比如?ABC，答案应该是4（AABC BABC CABC）。

我们可以考虑枚举B的位置，并以这个B为链接，那么问题就变成了统计左侧A的个数和右侧C的个数。这里也不能是简单地将左右两侧的A?和C?的个数乘起来，因为固定了某一对A、C后其他字符的变化也是要算作不同组合的。
我们将每一个B的位置的计数结果拆成四项来统计，即：

1
2
3
4
A、B、C
?、B、C
A、B、?
?、B、?

第一项很好统计，由于不存在?所以可以直接计数。
第二、三项的本质是相同的，我们在B的某一侧存在?时，要枚举任意一个?（让这个?作为A或C出现），那么其他位置的?则是任意的，那么每一个位置对答案的贡献是$3^{k-1}$，其中$k$为?的左侧或右侧总数。
第四项和第二、三项也是一样的，但是要在左右两边各取一个?，假设左侧有$x_1$个?，右侧有$x_2$个?，那么计数结果为$3^{x_1-1}×3^{x_2-1}$，整理为$3^{x_1+x_2-2}$。
这样我们就推出了每一个B对总体答案的分步贡献，我们维护A、C、?出现次数的前缀和，之后就可以分类讨论了。

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
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)

using LL = long long;
const int maxn = 100100;
LL mod = 1e9 + 7;
char s[maxn];
LL f[maxn][3];
int n;

LL mul(LL x, LL n) {
  LL ret = 1;
  while(n) {
    if(n & 1) {
      ret *= x; ret %= mod;
    }
    n >>= 1;
    x *= x; x %= mod;
  }
  return ret;
}

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%s", s+1)) {
    memset(f, 0, sizeof(f));
    n = strlen(s+1);
    for(int i = 1; i <= n; i++) {
      f[i][0] = f[i-1][0] + (s[i] == 'A');
      f[i][1] = f[i-1][1] + (s[i] == 'C');
      f[i][2] = f[i-1][2] + (s[i] == '?');
    }
    LL ret = 0;
    for(int i = 1; i <= n; i++) {
      if(s[i] == 'B' || s[i] == '?') {
        LL q = f[n][2] - (s[i] == '?');
        ret += mul(3LL, q) * (f[i-1][0] * (f[n][1] - f[i][1]) % mod);
        ret %= mod;
        if(q >= 1) {
          ret += mul(3LL, q-1) * (f[i-1][0] * (f[n][2] - f[i][2]) % mod);
          ret %= mod;
          ret += mul(3LL, q-1) * (f[i-1][2] * (f[n][1] - f[i][1]) % mod);
          ret %= mod;
        }
        if(q >= 2) {
          ret += mul(3LL, q-2) * (f[i-1][2] * (f[n][2] - f[i][2]) % mod);
          ret %= mod;
        }
      }
    }
    printf("%lld\n", ret);
  }
  return 0;
}