1040. 有几个PAT（25）

字符串APPAPT中包含了两个单词“PAT”，其中第一个PAT是第2位(P),第4位(A),第6位(T)；第二个PAT是第3位(P),第4位(A),第6位(T)。

现给定字符串，问一共可以形成多少个PAT？

输入格式：

输入只有一行，包含一个字符串，长度不超过10⁵，只包含P、A、T三种字母。

输出格式：

在一行中输出给定字符串中包含多少个PAT。由于结果可能比较大，只输出对1000000007取余数的结果。

输入样例：

APPAPT

输出样例：

2

//大概的思路就是计算每一个A之前的P的个数乘A之后T的个数，但是如果每一次遇到A都要计算一边的话肯定要超时，要用到动态规划

#include <iostream>
#include <string>

using namespace std;

long cntP[100000] = { 0 };
long cntT[100000] = { 0 };

int main(){
	string word; cin >> word;
	long cP=0, cT=0, cPAT=0;
	//从小标0开始向后遍历，如果遇到一个P，计数器+1，在当前位置记录从下标0开始到当前位置所有P的个数
	for (long i = 0; i < word.size(); ++i){
		if (word[i] == 'P'){
			cntP[i] = ++cP;
		}
		else{
			cntP[i] = cP;
		}
	}
	//从最后一位开始向前遍历，如果遇到一个T，计数器+1，在当前位置记录从下标0开始到当前位置所有T的个数
	for (long i = word.size() - 1; i >=0; --i){
		if (word[i] == 'T'){
			cntT[i] = ++cT;
		}
		else{
			cntT[i] = cT;
		}
	}

	//遍历时遇到A是，总计数起加上在这个点遇到P的个数乘以T的个数
	for (long i = 0; i < word.size(); ++i){
		if (word[i] == 'A'){
			cPAT += cntP[i] * cntT[i];
		}
	}

	cPAT %= 1000000007;

	cout << cPAT << endl;
	system("pause");
	return 0;
}