CF1917B

· · 题解

思路：

找规律题。

考虑对于 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;
}