AcWing 1583. PAT 计数—前缀和
原题链接
简单
作者:
春江花月夜ovo
,
2024-03-17 23:30:21
,
所有人可见
,
阅读 15
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int N = 1e5 + 10;
const int MOD = 1000000007;
int pre[N], last[N];
char g[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin >> g + 1;
int n = strlen(g + 1);
for (int i = 1; i <= n; i ++) pre[i] = pre[i - 1] + (g[i] == 'P');
for (int i = n; i; i --) last[i] = last[i + 1] + (g[i] == 'T');
i64 ans = 0;
for (int i = 1; i <= n; i ++)
{
if (g[i] == 'A') ans = (ans + pre[i] * last[i]) % MOD;
}
cout << ans << "\n";
return 0;
}