[ABC375D] ABA
[ABC375D] ABA
题意
给出一个由大写字母组成的长度为 \(n\) 的字符串 \(s\)，问长度为 \(3\) 的回文子序列数量。
思路
考虑枚举子序列中间的字符，则两边的字符需要相等，可以预处理出位置 \(i\) 左边和右边字符 \(c\) 的数量 \(L_{i,c} 和 R_{i,c}\)，则根据乘法原理可知答案为：
\[\sum_{i=2}^{n-1} \sum_{c=\text{'A'}}^{\text{'Z'}} L_{i,c}\times R_{i,c}
\]
代码
#include <bits/stdc++.h>
using namespace std;
string s;
long long cnt[128],cnt2[128],ans;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>s;
for(int i=2;i<s.length();i++)
cnt[s[i]]++;
for(int i=1;i<s.length();i++){
cnt2[s[i-1]]++;
for(int v='A';v<='Z';v++)
ans+=cnt[v]*cnt2[v];
cnt[s[i+1]]--;
}
cout<<ans;
return 0;
}