先数出到i为止P的个数
然后数出到i为止A的个数加上之前P的个数
最后遇到T再累加就好。
记得00000007
………………………………更新线…………………………
想到了一个新的办法
preP【i】保存当前【i】之前包括【i】的P的个数
afterT【i】保存当前【i】之后包括【i】的T的个数
这样遇到A的时候preP【i】* preP【i】就好~
#include <iostream> #include <algorithm> #include <cstring> #include <climits> #include <string> #include <vector> #include <map> #include <set> #include <queue> #include <stack> #define MAX 100010 using namespace std; string s; int preP[MAX]; int afterT[MAX]; long long ans; int main(){ cin >> s; int cp = 0; for(int i = 0; i < s.size() ;i ++){ if(s[i] == 'P'){ cp++; } preP[i] = cp; } int ct = 0; for(int i = s.size() - 1; i >= 0;i --){ if(s[i] == 'T'){ ct++; } afterT[i] = ct; } for(int i = 0 ;i < s.size() ;i++){ if(s[i] == 'A'){ ans += (preP[i] * afterT[i]); } } cout << ans % 1000000007 << endl; return 0; }………………………………结束………………………………………………………… #include <iostream> #include <string> #include <vector> using namespace std; vector <int> CountP; vector <int> CountA; string s; int sum = 0; int NowP = 0, NowA = 0; int main() { getline(cin, s); CountP.resize(s.size()); CountA.resize(s.size()); for (int i = 0; i < s.size(); i++) { if (s[i] == 'P') { NowP++; } CountP[i] = NowP; } for (int i = 0; i < s.size(); i++) { if (s[i] == 'A') { NowA += CountP[i]; } CountA[i] = NowA; } for (int i = 0; i < s.size(); i++) { if (s[i] == 'T') { sum += CountA[i]; if (sum > 1000000007) sum = sum % 1000000007; } } cout << sum << endl; return 0; }