c++ 题解 | #abb#

cnt['c']记录字符'c'出现的次数
dp['c']记录以字符'c'结尾的长度为2的子序列的个数，就是"*c"这种形式，两个字符是不一样的，就是叠词的前两个字符。

1. 遍历s中的每个字符，假设i=k时，遇到字符x，res = res + dp[x]，就是s[0~k-1]中的答案数加上遍历到字符结尾的长度为2的子序列的个数(之前长度为2，现在遇到了x，就满足叠词要求，dp[x]就是由于遍历到了x字符，新出现的叠词数)
2. 那遇到新的x，记录字符'c'结尾的长度为2的子序列的个数也要更新：dp[x] = 之前的数量+遍历到的这个x所能形成的个数=dp[x] + (i-cnt[x])。这里i-cnt[x]是到目前位置，x之前有（i-cnt[x]）个与x不用的字符，它们可以和这个x形成（i-cnt[x]）个长度为2的子序列。
3. 最后更新 字符x出现的次数 ++cnt[x]

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
typedef long long LL;
LL dp[26];
LL cnt[26];
int main() {
    int n;
    scanf("%d", &n);
    getchar();
    char *s = (char*)malloc(n+1);
    scanf("%s",s);

    LL res = 0;
    for(int i = 0; i < n; i++)
    {
        res += dp[s[i] - 'a'];
        dp[s[i]-'a'] += i - cnt[s[i] - 'a'];
        ++ cnt[s[i]-'a'];
    }
    printf("%lld", res);

    return 0;
}
// 64 位输出请用 printf("%lld")