1040 有幾個PAT (25分)(20行以内的代碼)

字元串 APPAPT 中包含了兩個單詞 PAT，其中第一個 PAT 是第 2 位§，第 4 位(A)，第 6 位(T)；第二個 PAT 是第 3 位§，第 4 位(A)，第 6 位(T)。

現給定字元串，問一共可以形成多少個 PAT？

輸入格式：

輸入隻有一行，包含一個字元串，長度不超過10^​5，隻包含 P、A、T 三種字母。

輸出格式：

在一行中輸出給定字元串中包含多少個 PAT。由于結果可能比較大，隻輸出對 1000000007 取餘數的結果。

輸入樣例：

APPAPT

輸出樣例：

2

思路：用f數組記錄所有周遊過的A和T的組合總數，當遇到P時直接加上f[t-1]就可以了。

#include<bits/stdc++.h>
using namespace std;
int f[100000],t=0;
int main()
{
	long long a=0,b=0;
	string s;
	cin>>s;
	long long temp=s.size()-1,sum=0;
	for(int i=temp;i>=0;i--){
		if(s[i]=='A'){
      		f[t]=b+f[t-1];
     		t++;
    	}
		if(s[i]=='T') b++;
		if(s[i]=='P') sum=(sum+f[t-1])%1000000007;
	}
	cout<<sum;
}