1.求出给定字符串中，PAT的组合数。
2.这道题目比较有趣，我的思路如下：
1）首先统计countP[i]，即0~i的位置上，一共有多少个P，同理可以反向统计出countT[i],即i到n-1之间有多少个T。
2）遍历string，当str[i]==‘A’时，那么ans+=countP[i-1]*countT[i+1]，当然， 需要根据题目要求，对100000007取模。
The string APPAPT contains two PAT‘s as substrings. The first one is formed by the 2nd, the 4th, and the 6th characters, and the second one is formed by the 3rd, the 4th, and the 6th characters.
Now given any string, you are supposed to tell the number of PAT‘s contained in the string.
Input Specification:
Each input file contains one test case. For each case, there is only one line giving a string of no more than 105characters containing only P, A, or T.
Output Specification:
For each test case, print in one line the number of PAT‘s contained in the string. Since the result may be a huge number, you only have to output the result moded by 1000000007.
Sample Input:
APPAPT
Sample Output:
2
AC代码：
[c language=”++”]
//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
#define maxDivide 1000000007
int main(void)
{
string str;
cin >> str;
int *countP = new int[str.size()];
int *countT = new int[str.size()];
memset(countP, 0, sizeof(countP));
memset(countT, 0, sizeof(countT));
if (str[0] == ‘P’) countP[0] = 1;
if (str[str.size() – 1] == ‘T’) countT[str.size() – 1] = 1;
for (int i = 1; i < str.size(); i++)
{
if (str[i] == ‘P’)
countP[i] = countP[i – 1] + 1;
else
countP[i] = countP[i – 1];
}
for (int i = str.size()-2; i >=0; i–)
{
if (str[i] == ‘T’)
countT[i] = countT[i + 1] + 1;
else
countT[i] = countT[i + 1];
}
unsigned long long ans = 0;
for (int i = 1; i < str.size() – 1; i++)
{
if (str[i] == ‘A’)
{
unsigned long long tmp = (countP[i – 1] * countT[i + 1]) % maxDivide;
ans += tmp;
ans = ans%maxDivide;
}
}
cout << ans << endl;
return 0;
}
[/c]