这是活用递推里面比较经典的一种题型；

如果采用最简单的暴力枚举，则会出现time limited错误。这道题关键是能够找到递推的思路。对于序列中的每一个每一个A，如果能够有PAT出现，则必定A的左右都有P和T；如果A左边有a个P，右边有b个T，则可以推出含有该A的PAT有a*b个；所以解法就被分解成以下几个步骤：1.寻找左边P的个数；2.寻找右边T的个数；3.遍历A，进行左右的乘积；至于P和T个数的保存，我们可以仿照迪杰斯特拉算法中的distance数组来进行构造；首先对于保存P的数组，进行输入数组的遍历，每一次从前一位继承P的数目，如果该位为P，则数目加一，从而构成一个保存的P的数组，其中index索引处的值代表输入序列index位的左边P的个数；相关代码如下：

int len=strlen(str);    for(int i=0;i
    
     0){            leftNumP[i]=leftNumP[i-1];        }        if(str[i]=='P'){            leftNumP[i]++;        }    }
    

对于T，则没必要构建数组，因为可以在计数的同时从后往前遍历，这样就将第三第四步结合在了一起；

相关代码如下;

nt ans=0,rightNumT=0;    for(int i=len-1;i>=0;i--){        if(str[i]=='T'){            rightNumT++;        }else if(str[i]=='A'){            ans=(ans+leftNumP[i]*rightNumT)%MOD;        }    }

从而可以通过一次遍历完成后两步的任务；

总体代码如下所示：

#include
    
     #include
     
      #include
      
       const int MAXN=100010;const int MOD=1000000007;char str[MAXN];int leftNumP[MAXN]={0};int main(){    scanf("%s",str);    int len=strlen(str);    for(int i=0;i
       
        0){            leftNumP[i]=leftNumP[i-1];        }        if(str[i]=='P'){            leftNumP[i]++;        }    }    int ans=0,rightNumT=0;    for(int i=len-1;i>=0;i--){        if(str[i]=='T'){            rightNumT++;        }else if(str[i]=='A'){            ans=(ans+leftNumP[i]*rightNumT)%MOD;        }    }    printf("%d\n",ans);    system("pause");    return 0;}