Solution

按照一般的计数 dp 的状态设计，我们不妨设 \(f_i\) 为以 \(i\) 为右端点的合法子串个数。

最后答案是 \(\sum_{i=1}^{n} f_i\)。

考虑合法的子串有哪几种形式，不妨设 \(A,B\) 均合法，以及单个字符 \(c\)。

那么合法的字串只可能为一下四种形式：

\(A\)
\(AB\)
\(cAc\)
\(cc\)

其他所有的都可以规约到这四种。

设 \(lst_i\) 为最大的 \(j\) 满足 \(s_{[i,j]}\) 是合法子串的 \(j\)。

那我们的转移便是 \(f_i = f_{lst_i - 1} + 1\)。

加 1 是因为要把自己算上，前面的 \(f_{lst_i - 1}\) 是在算第二类子串的个数。

对于 \(lst_i\) 的计算直接采取暴力跳的方式即可，考虑每次跳的一定是不同字符，总复杂度是 \(O(26n)\)。

code

#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = (j); i <= (k); i ++)
#define per(i, j, k) for(int i = (j); i >= (k); i --)
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e6 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n;
string s;
LL f[N];
int lst[N];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> s;
	s = " " + s;
	rep(i, 1, n) {
		lst[0] = -1;
		if(s[i] == s[i - 1]) lst[i] = i - 1;
		else {
			lst[i] = -1;
			int j = i - 1;
			while(lst[j] != -1) {
				j = lst[j] - 1;
				if(s[i] == s[j]) {
					lst[i] = j;
					break;
				}
			}
		}
	}
	rep(i, 1, n) if(lst[i] != -1) f[i] = f[lst[i] - 1] + 1;
	LL res = 0;
	rep(i, 1, n) res += f[i];
	cout << res << '\n'; 
	return 0;
}