PAT A1093 Count PAT‘s (25分)
前言
正文
参考题解
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
/* 题意：对于给定的字符串（只包含'P','A','T'），求其包含PAT的个数 思路：遍历每个'A'，其左边的'P'的个数与右边的'T'的个数乘积就是 这个'A'所能组成"PAT"的个数。 注意：需要将输出结果res%1000000007（在每次计算过程中以及最后输出res时都要取余） */
const int N=1e5+10;
string str;
int p[N],t[N];//p[i]和t[i]分别表示第i号字符左边的'P'的个数和右边'T'的个数
int main(){
cin>>str;
int cntP=0,cntT=0;
int len=str.size();
for(int i=0;i<len;i++){
if(str[i]=='P')cntP++;
p[i]=cntP;
}
long long res=0;
for(int i=len-1;i>=0;i--){
if(str[i]=='T')cntT++;
if(str[i]=='A')res+=(p[i]*cntT)%1000000007;
}
cout<<res%1000000007<<endl;
return 0;
}
