1093. Count PAT's.md

pat 甲级 1093. Count PAT's、乙级 1040. 有几个 PAT

题意概述

字符串 APPAPT 中包含了两个单词 PAT，其中第一个 PAT 是第 2 位(P)，第 4 位(A)，第 6 位(T)；第二个 PAT 是第 3 位(P)，第 4 位(A)，第 6 位(T)。

现给定字符串，问一共可以形成多少个 PAT？

输入输出格式

输入只有一行，包含一个字符串，只包含 P、A、T 三种字母。

在一行中输出给定字符串中包含多少个 PAT。由于结果可能比较大，只输出对 $1000000007(10^9+7)$取余数的结果。

数据规模

输入的字符串长度不超过$10^5$。

算法设计

直接暴力枚举会超时，可以根据字符A来简化运算。对于每一个字符A，包含它的PAT字符串的数量应该等于该字符左侧的P字符数量乘该字符右侧T字符的数量。根据这个性质，问题就变成了如何统计所有A字符左侧P字符的数量和其右侧T字符的数量。

可以用两个数组p和t分别记录字符左侧的P字符数量和该字符右侧T字符的数量，遍历一次字符串，累加所有A字符左侧P字符的数量和其右侧T字符的数量即可。注意别忘记对$10^9+7$取模。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string si;
    cin >> si;
    const gg mod = 1e9 + 7;
    vector<gg> p(si.size()), t(si.size());
    for (gg i = 1; i < si.size(); ++i) {
        p[i] = p[i - 1] + (si[i - 1] == 'P');
    }
    for (gg i = si.size() - 2; i >= 0; --i) {
        t[i] = t[i + 1] + (si[i + 1] == 'T');
    }
    gg ans = 0;
    for (gg i = 0; i < si.size(); ++i) {
        if (si[i] == 'A') {
            ans = (ans + p[i] * t[i]) % mod;
        }
    }
    cout << ans;
    return 0;
}