【暴力求解版本-15分】
#include <bits/stdc++.h>
using namespace std;
char s[100010];
int p[100010];
int a[100010];
int t[10010];
int main(void)
{
int res=0,np=0,na=0,nt=0;
scanf("%s",s);
for(int i=0;i<strlen(s);i++)
{
if(s[i]=='P')
{
p[np]=i;np++;
}
else if(s[i]=='A')
{
a[na]=i;na++;
}
else if(s[i]=='T')
{
t[nt]=i;nt++;
}
}
for(int i=0;i<np;i++)
{
for(int j=0;j<na;j++)
{
if(p[i]>a[j]) continue;
for(int k=0;k<nt;k++)
{
if(a[j]>t[k]) continue;
else
{
res = (res+nt-k)%1000000007;
break;
}
}
}
}
printf("%d",res);
}
【O(n)时间复杂度版本-25分】
思想：对于一个确定位置的A，其形成的PAT个数 = 他左边P的个数 * 他右边T的个数。注意，为了避免O(n^2)时间复杂度，我们先对整个字符串进行两次遍历来使后面的计算过程可以达到O(1)级别。
#include <bits/stdc++.h>
using namespace std;
char s[100010];
int p[100010]; //p in left
int t[100010]; //t in left
int main(void)
{
int res=0,len;
scanf("%s",s);
len=strlen(s);
p[0]=0;t[0]=0; //initially
for(int i=0;i<len;i++)
{
if(s[i]=='P')
{
p[i+1]=p[i]+1;
t[i+1]=t[i];
}
else
{
p[i+1]=p[i];
if(s[i]=='T') t[i+1]=t[i]+1;
else t[i+1]=t[i];
}
}
for(int i=0;i<len;i++)
{
if(s[i]=='A')
{
res = (res+p[i]*(t[len]-t[i]))%1000000007;
}
}
printf("%d",res);
}