水题,考虑直接倒序更新,一边更新一边维护 每种字符的后缀数量和 suf[c],然后动态更新sum = $\sum (suf[c] - 1) * suf[c] / 2$,最后更新答案 ans += sum - sum (suf[s[i]] - 1) * suf[s[i]] / 2,即可。
#include <bits/stdc++.h> using i64 = long long; int main() { std::cin.tie(nullptr)->sync_with_stdio(false); int n; std::string s; std::cin >> n >> s; std::vector<int> suf(26); i64 sum = 0; i64 ans = 0; for (int i = n - 1; i >= 0; i--) { ans += sum - (suf[s[i] - 'a'] - 1) * suf[s[i] - 'a'] / 2; sum -= (suf[s[i] - 'a'] - 1) * suf[s[i] - 'a'] / 2; suf[s[i] - 'a']++; sum += (suf[s[i] - 'a'] - 1) * suf[s[i] - 'a'] / 2; } std::cout << ans; return 0; }