题解 | #【模板】前缀和#

#include "stdio.h" #include "string.h" #define N 400000 int main(){ long long int n,i,j; char a[N]; scanf("%lld",&n); for(i=0;i<n;i++){ scanf(" %c",&a[i]); } long long int sum[n+1][26]; memset(sum,0,(n+1)26sizeof(long long int)); for(i=n-1;i>=0;i--){ int num=a[i]-'a'; sum[i][num]++; for(j=0;j<26;j++){ sum[i][j]+=sum[i+1][j]; }

} long long int dp[N]={0}; long long int sum1=0; for(i=1;i<=n;i++){ for(j=0;j<26;j++){

    if(j!=(a[i-1]-'a')){
        dp[i]+=(sum[i-1][j]*(sum[i-1][j]-1))/2;
    }
}
sum1+=dp[i];

} printf("%lld",sum1);

}