patA1093可以再简单一点点，时间复杂度大概从2n变成n

[J-bz]

只用一次循环就ok啦。 `#include #include using namespace std;

int main() { string str; cin >> str; long long p = 0; long long a = 0; int begin = 0; while(str[begin] != 'P') { begin++; } long ans = 0; int len = str.length(); for(int i = begin; i < len; i++) { if(str[i] == 'P') { p++; } else if(str[i] == 'A') { a = a + p; } else if(str[i] == 'T') { ans = ans + a; } } printf("%lld", ans % 1000000007); return 0; } `

[J-bz]

不知道为什么代码变成了这样，我放图片吧。

[liuchuo]

重新看了下我的代码，貌似也只用了一层for循环，和你的复杂度是一样的，不知道是我之前更新过代码了还是什么别的原因，代码如下：

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    cin >> s;
    int len = s.length(), result = 0, countp = 0, countt = 0;
    for (int i = 0; i < len; i++) {
        if (s[i] == 'T')
            countt++;
    }
    for (int i = 0; i < len; i++) {
        if (s[i] == 'P') countp++;
        if (s[i] == 'T') countt--;
        if (s[i] == 'A') result = (result + (countp * countt) % 1000000007) % 1000000007;
    }
    cout << result;
    return 0;
}

PS：代码格式化用三个`包围就可以啦

[W1llyu]

可以这么改，只需要一次循环

#include <iostream>
#define BASE 1000000007
using namespace std;

int p = 0, pa = 0, pat = 0;
string str;
int main () {
	cin >> str;
	for (int i=0; i<str.length(); i++) {
		if (str[i] == 'P') {
			p++;
		} else if (str[i] == 'A') {
			pa += p;
		} else if (str[i] == 'T') {
			pat += pa;
			if (pat >= BASE) pat = pat % BASE;
		}
	}
	cout << pat << endl;
	return 0;
}