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;
}