这题出现在“活用递推”专题下面,所谓递推就是这一步的结果和上一步的结果有直接联系。对于本题来说,从左到右,记到当前位置,一共出现的P的个数,如果当前位置是P,则个数就是上一位的加1,否则等于上一位。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
#include<stdlib.h>
#include<time.h>using namespace std;
typedef long long LL;const int maxn = 100010;
const int MOD = 1000000007;
const int INF = 1000000000;//INF:下确界
const LL SUP = (1LL<<63)-1;//SUP:上确界
const double eps = 1e-5;int main(){char str[maxn];int count_P[maxn];int count_T[maxn];scanf("%s",str);int len = strlen(str);//从头到尾,数Pif(str[0]=='P')count_P[0]=1;else count_P[0]=0;for(int i=1;i<len;i++){if(str[i]=='P')count_P[i]=count_P[i-1]+1;else count_P[i]=count_P[i-1];}//从尾到头,数Tif(str[len-1]=='T')count_T[len-1]=1;else count_T[len-1]=0;for(int i=len-2;i>=0;i--){if(str[i]=='T')count_T[i]=count_T[i+1]+1;else count_T[i]=count_T[i+1];}//对于下标在1~len-2上的A逐个记组成PAT的数量LL res = 0;for(int i=2;i<=len-1;i++){if(str[i]=='A')res += (LL)count_P[i]*count_T[i];}int count = res%(LL)MOD;printf("%d",count); return 0;
}