PTA（乙级）1040 有几个PAT（C语言）

1040 有几个PAT (25 分)

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

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

输入格式：

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

输出格式：

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

输入样例：

APPAPT

结尾无空行

输出样例：

 

2

结尾无空行

思路：

        遍历暴力解会导致时间超时

        问题关键在于要先有P，再有A，最后再有T；才能组成一个PAT。同时也可以注意到，

        组合数 = 在前面的P的数量 * 在中间的A的数量 * 在后面的T的数量

        这样算出每一个的数量过于复杂，所以不妨换个思路， 我们不必先求出合适P，A，T的数量，而是在遇到P，A，T时对数据先进行处理，已经知道要先有P，再有A，最后再有T，所以我们不妨先从后面来遍历字符串数组，遇到T时让T的数量t+1；遇到A时让y += 1*t,同时让 a = 0（一个A只能与同一个T组合一次）; 当遇到T时，再 sum += 1*y（一个T只能与同一组A和T组合一次）;

这样便可以得出结果

代码详细：

#include
#include
//#include
#define MOD 1000000007
int main() {
	char x[100000];
	scanf("%s",x);
	int t = strlen(x);
	//int *A, *T;
	//A = (int* )malloc(sizeof(int)* t);
	//T = (int* )malloc(sizeof(int)* t);
	int i, j, tmp1, tmp2 ;
	long long int y = 0;
	long long int sum = 0;
	tmp1 = 0;
	tmp2 = 0;
	for(i= t-1; i >= 0; i--) {
		
		if(x[i] == 'A') {
			//tmp1++;
			//y += (tmp1 * tmp2) % MOD;//防止PTA 
			//tmp1 = 0;//PTATA
			y += tmp2 % MOD;
		} else if( x[i] == 'T') {
			tmp2++;
		} else if(x[i] == 'P') {
			sum = (sum + y) % MOD;
			//tmp1 = 0;
			//tmp2 = 0;
		}

	}

	printf("%d",sum);
	return 0;

}