本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-25 18:27:44

思路：

找规律题。

考虑对于 $s1,s2,\dots,s6$ 的情况。

$$s1,s2,s3,s4,s5,s6$$ $$s1,s3,s4,s5,s6$$ $$s2,s3,s4,s5,s6$$ $$s1,s4,s5,s6$$ $$s2,s4,s5,s6$$ $$s3,s4,s5,s6$$ $$s1,s5,s6$$ $$s2,s5,s6$$ $$s3,s5,s6$$ $$s4,s5,s6$$ $$s1,s6$$ $$s2,s6$$ $$s3,s6$$ $$s4,s6$$ $$s5,s6$$ $$s1$$ $$s2$$ $$s3$$ $$s4$$ $$s5$$ $$s6$$

我们发现按长度排序，那么对于长度为 $i$ 的，那么前 $n - i + 1$ 个数是前缀，而后缀都相同，然后每次枚举就行了。

Code:

#include <bits\/stdc++.h>

using namespace std;

int T;
int n;
string s;
bool st[200010][30][30];
bool st1[30];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	cin >> T;
	while (T--) {
		cin >> n >> s;
		int cnt = 0;
		long long ans = 0;
		for (int i = 0; i < n; ++i) {
			if (!st1[s[i] - 'a']) ++cnt;
			ans = 1ll * ans + 1ll * cnt;
			st1[s[i] - 'a'] = true;
		}
		printf("%lld\n", ans);
		memset(st1, false, sizeof(st1));
	}
	return 0;
}