AcWing 1583. PAT 计数
原题链接
简单
作者:
sy123
,
2021-01-06 20:45:27
,
所有人可见
,
阅读 367
#include<bits/stdc++.h>
#define MOD 1000000007;
using namespace std;
const int N=100010;
typedef long long LL;
char s[N];
int lenp[N],lent[N];
int main(){
scanf("%s",s+1);
int len=strlen(s+1);//注意这边s+1
for(int i=1;i<=len;i++){
if(s[i]!='P')
lenp[i]=lenp[i-1]; //lenp[i]表示左边包括它本身有多少个P
else
lenp[i]=lenp[i-1]+1;
}
for(int i=len;i>0;i--){
if(s[i]!='T')
lent[i]=lent[i+1]; //lent[i]表示右边包括它本身有多少个T
else
lent[i]=lent[i+1]+1;
}
LL res=0;
for(int i=1;i<=len;i++){
if(s[i]=='A'){
res=(res+(lenp[i-1]*lent[i+1]))%MOD;//左边P的个数乘T的个数
}
}
cout<<res<<endl;
return 0;
}