PAT.1040. 有几个PAT

题目

时间限制
120 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
作者
CAO, Peng
字符串APPAPT中包含了两个单词“PAT”，其中第一个PAT是第2位(P),第4位(A),第6位(T)；第二个PAT是第3位(P),第4位(A),第6位(T)。
现给定字符串，问一共可以形成多少个PAT？
输入格式：
输入只有一行，包含一个字符串，长度不超过10 5 ${}^5$，只包含P、A、T三种字母。
输出格式：
在一行中输出给定字符串中包含多少个PAT。由于结果可能比较大，只输出对1000000007取余数的结果。
输入样例：

APPAPT

输出样例：

2

分析：

咦读题好像不难，当发现第一个P，再继续找下一个A，再继续找下一个T，就是三个for而已，提交

哈哈哈哈那你可就太天真了

我们来看看正确姿势
1.既然我们要找之后的A的个数和T的个数，那我们从最后开始找
2.考虑每次遇到A和T就对对应的标记加一，这样当遇到P的时候直接标记数乘就行啦！（才怪勒）
3.之所以不能直接相乘，是因为比如 PATTATT，从后到前遇到P时，A有2个，T有4个，能组成8个么？不现实吧。实际的情况应该是，从最后开始，遇到T记数，再遇到T计数，遇到A了，此时只要再遇到P这就有两种方案了，所以我们存下此时的方案数量，继续，又遇到两个T，计数，又遇到A，连同后面的T，此时A这里遇到P就能有4种方案数，再继续遇到P，则2+4=6了。

代码（cpp）

#include<iostream>
#include<string.h>
using namespace std;
int A[100000+5]={0};
int main(){
    char a[100000+5];
    int sum=0,t=0;
    gets(a);
    for(int i=strlen(a)-1;i>=0;i--){
        if(a[i]=='P'){
            A[i]=A[i+1];
            sum+=A[i];
            sum%=1000000007;
        }
        else if(a[i]=='A'){
            A[i]=A[i+1]+t;
            A[i]%=1000000007;
        }
        else if(a[i]=='T'){
            t++;
            A[i]=A[i+1];
        }
    }
    cout<<sum;
    return 0;
}