2020 ICPC EC-Final A题

spirit

2021 年 08 月 11 日

1951 次浏览

暂无评论

1462字数

算法竞赛动态规划

# Gym103069  A-Namomo Subsequence

[2020 ICPC EC-Final A题](https://codeforces.com/gym/103069/problem/A)

## 题意

给定一个字符串 $s$ ，$|s| \leq 1e6$ 。求有多少个形如 $namomo$ 的子序列。

**input**

```
wohaha

momomo

gshfd1jkhaRaadfglkjerVcvuy0gf

retiredMiFaFa0v0
```

**output**

```
1

33
```

## 思路

遍历每一个 $s_i$ 当作 $m$ ，枚举 $o$ ，容斥求 $na$ 的数量，$DP$ 求 $omo$ 的数量。

记 $sum$ 为 $s[1, i - 1]$ 中不对 $na$ 做任何限制情况下的数量，$cnt_{i, j}$ 为指定 $n = i, a = j$ 的数量。

那么要求的 $na$ 数量为 $cnt = sum - cnt_{*,o} - cnt_{o, *} - cnt_{*, m} - cnt_{m, *} + cnt_{m, o} + cnt_{o, m}$ 。

定义 $dp_{m, o, 0}$ 为 $s[i, n]$ 中 $mo$ 的数量，$dp_{m, o, 1}$ 为 $s[i, n]$ 中 $omo$ 的数量, $suc_i$ 为 $[i, n]$ 中 $i$ 的数量。显然有转移方程：

$$
\begin{equation}\begin{split}
dp_{m, o, 1} = dp_{m, o, 1} + dp_{m, o, 0}, \ o = s_i \\
dp_{m, o, 0} = dp_{m, o, 0} + suc_o, \ m = s_i \\
\end{split}\end{equation}
$$

## 代码

```cpp
#pragma GCC optimize(2)
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, M = 62;
const int mod = 998244353;
int dp[M][M][2], pre[M], suc[M], s[N];
 
int fastPow(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = (LL)res * a % mod;
        k >>= 1;
        a = (LL)a * a % mod;
    }
    return res;
}
int main(int argc, char const *argv[]) {
    int res = 0, tn = fastPow(2, mod - 2), n = 0;
    char c;
    while (~(c = getchar()) && c != '\n') {
        if (c >= 'a' && c <= 'z') c -= 'a';
        else if (c >= 'A' && c <= 'Z') c = c - 'A' + 26;
        else c = c - '0' + 52;
        pre[c]++;
        s[++n] = c;
    }
    for (int i = n; i; i--) {
        pre[s[i]]--, suc[s[i]]++;
        LL sum = 0;
        for (int c = 0; c < 62; c++) {
            sum += (LL)(i - 1 - pre[c]) * pre[c];
        }
        for (int c = 0; c < 62; c++) {
            if (c == s[i]) continue;
            LL m = (LL)(i - 1 - pre[s[i]]) * pre[s[i]];
            LL o = (LL)(i - 1 - pre[c]) * pre[c];
            int x = (sum - 2 * (m + o) + 2ll * pre[s[i]] * pre[c]) % mod * tn % mod;
            if (x < 0) x += mod;
            res = (res + (LL)x * dp[s[i]][c][1]) % mod;
            dp[c][s[i]][1] = (dp[c][s[i]][1] + dp[c][s[i]][0]) % mod;
            dp[s[i]][c][0] = (dp[s[i]][c][0] + suc[c]) % mod;
        }
    }
    printf("%d\n", res);
    return 0;
}
```

最后修改：2021 年 08 月 11 日