题目:

count PAT's
输入一串字符，其中字符集为 {P,A,T}， 求解字符中包含多少个PAT子序列。
例如：PATT 包含2个PAT 子序列， PAATT包含4个PAT子序列。

问题分析：

对于字符串s[n]， 考虑某位置s[i]，相对于s[i-1]增加了s[i]，考虑增加s[i]对PAT子序列的影响：
如果s[i]是T字符，那么当前的PAT子序列增加的数目，就是当前PA子序列的数目，因为前面有多少个PA，增加一个T，就会增加多少个PAT；
同理，如果s[i]是A字符，那么当前的PA 的增加数目，就是当前的P的字符数目。

复杂度分析

只需要简单的遍历一遍s[n]，复杂度为O(n)

通过代码

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;

char s[100002];
int size;
const int mod = 1000000007;

int main() {
    int p=0,pa=0,pat=0;

    cin >> s;
    int n = strlen(s);
    for (int i=0;i<n;i++) {
        if (s[i] == 'P') {
            p++;
        }

        if (s[i] == 'A') {
            pa+=p;
            pa%=mod;
        }

        if (s[i] == 'T') {
            pat+=pa;
            pat%=mod;
        }
    }
    cout << pat<<endl;
}