PTA A_1093 Count PAT's

798236606

题目链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805373582557184

解：递推法

#include <stdio.h>
#include <string.h>

typedef long long int LL;

char str[100010];
int P_num[100010];
int T_num[100010];

int main(void)
{
        int i, len;
        LL count = 0;
        
        gets(str);
        
        len = strlen(str);
        
        P_num[0] = (str[0] == 'P') ? 1 : 0;
        T_num[len - 1] = (str[len - 1] == 'T') ? 1 : 0;
        
        for (i = 1; i < len; i++)
                P_num[i] = (str[i] == 'P') ? (P_num[i - 1] + 1) : P_num[i - 1];

        for (i = len - 2; i >= 0; i--)
                T_num[i] = (str[i] == 'T') ? (T_num[i + 1] + 1) : T_num[i + 1];

        for (i = 0; i < len; i++)
                if (str[i] == 'A')
                        count += (LL)P_num[i] * (LL)T_num[i];

        printf("%d", count % 1000000007);
        
        return 0;
}