题目描述

对于一个字符串 S，我们定义 S 的分值为f(S) ,f(S)为 S 中出现的不同的字符个数。

例如 f(“aba”)=2，f(“abc”)=3，f(“aaa”)=1。

现在给定一个字符串 S[0 \dots n-1]（长度为 n），请你计算对于所有 S 的非空子串 S[i \dots j]（0 \le i \le j < n），f(S[i \dots j]) 的和是多少。

输入描述 输入一行包含一个由小写字母组成的字符串 S。 其中，1 \le n \le 10^5。

输出描述 输出一个整数表示答案。

输入输出样例 示例 输入 ababc 输出 28

运行限制 最大运行时间：1s 最大运行内存: 128M。

题目注意事项:题目描绘的子串必须是连续的，中间不存在间断，如abcd，abc可以是子串，但是abd不能是子串

解题思路:

这道题有什么适合什么解题方法?

一看到这道题，我首先就会像能不能用一个一个枚举出来，仔细思考，使用枚举的话就会用大于或等于两层循环，按照题目给的n的极限数量来计算，时间复杂度会大于n^2，也就是大于100亿，显然不可能一一枚举，所以我就想另外的方法，这里要计算在子串中出现不同字符的个数，一个子串中无论有多少个相同的字符a，那它也只计算一次，也就是说，我所关心的不是子串的全部字母，而是子串中互不相同的字母，比如说ababcca中，我只关心这里面有a,b,c，他们的数量，排列什么之类的我一律不关心，也就是代表着，这个子串每个元素我都看作一个独立的个体，再进一步地想，我需不需要把全部个体都要考虑，显然不需要，比如说ababcca，你知道了a出现在第一个位置，也就确认了这个字符串中有a这个字符，其他的a就没必要考虑了，所以我只想要关心这个子串中某个字符出现与否，如果出现了，那么我就说它在这道题中贡献了1，当我把子串中全部字符的贡献加总在一起，那就是这个子串中元素不同的个数了

这就是贡献计算的思想，如果答案的总和，可以拆成各个因子单独带来的加分，并且一个因子的加分，不会和别的因子互相重复统计，那么总答案 = 所有因子的贡献相加。

如何使用贡献计算来解题？

同时对全部独立元素进行贡献计算是不太现实的，那我们可以对一个一个元素进行贡献计算，前面说了，我对这个子串有多少个字符，子串里面元素的排列不感兴趣，那么我们就可以把一个个子串抽象成一个起点到终点的一个整体，如果说这个整体里面有一个我希望的字符，就让它的贡献加1。

引出一个问题，起点和终点怎么取，怎么确定里面是否有我想要的字符？

这道题里面我只知道字符串S，其他的一概不知，当我走过每一个字符串里面的字符时，我能知道我现在走的字符是哪个字符，那我可以发挥主观能动性，我走到的字符就是我想要的字符，既然走到了，那它就必然存在，贡献值必然加1

前面说我既然知道一个字符出现了一次，那后面出现多少次这个字符与我没有任何关系，那么我为什么不能把我走到的这个字符定义成它在子串中第一次出现的地方呢

既然它是第一次出现，那么前面就不应该再出现一次这个字符，那么我可以把起点定在前面与它相同元素出现时候的位置的后一个位置，我不关心后面它是否又出现一次，那么终点可以一直延伸到字符串末尾，这个终点可以取自己本身，可以取它下一个元素，也可以一直取到末尾，有很多种可能性。

利用乘法原理，我确认一个子串需要两步:1.确认起点，2.确认终点,3.起点和终点相乘就是全部可能的子串的个数，这个子串集合中，每一个子串都有共同的特点，就是我所走到的元素都在里面贡献了1，那么它的总贡献就是子串个数*1

我每走一步，就能算出我脚下的那个元素做出的贡献，全部元素的贡献，就是它代表着它这个元素首次出现的位置

1. 随便挑任意一个子串（全部子串里任意一个都满足）
2. 它里面每一种不同字符，都有唯一的首次出现位置
3. 这个子串会被算进的贡献里
4. 同一种字符不会被多个位置重复统计
5. 不同字符各自认领自己的 1 分，叠加起来正好是这个子串应该有的分值

初始代码：

#include <stdio.h>
#include <string.h>
char str[100000]; 
int main(void)
{
	long long int ans=0,front_sum,back_sum;
	long long int comb_sum,x,y,totnum; 
	scanf("%s",&str);
	totnum = strlen(str); 
	
	for(x=0;x<totnum;x++)
	{
		int check = 0;
		for(y=0;y<x;y++)
		{
			if(str[y]==str[x])
			{
				front_sum = x-y;//这里可以算前和（离x最近的与x相同元素的y的差值就是y到x中间元素再加上x本身的值）
				check = 1;
			} 
		}
		if(check == 0)//如果前面没有元素和它相等的话，check值为0 ,这时候前面的全部位置都能选 
		{
			front_sum = x+1;
		}
		
		back_sum = totnum - x;//得到的数就是x出发到最后一个元素的元素的总和（包括x自己）
		comb_sum = back_sum * front_sum;//组合数就是前和与后和相乘
		ans += comb_sum;
	}
	printf("%lld",ans);
	return 0;
}

因为双重循环的原因，部分超时，只有百分之六十的通过率,所以优化了代码:

<code>#include <stdio.h>
#include <string.h>
char str[100000];
int last[26];//26个字母上次出现的位置 
int main(void)
{
	long long int ans=0,front_sum,back_sum;
	long long int comb_sum,x,y,totnum; 
	scanf("%s",&str);
	totnum = strlen(str); 
	for(x=0;x<26;x++)
	{
		last[x] = -1;
	} 
	
	for(x=0;x<totnum;x++)
	{
		int char_num = str[x] - 'a';//得到字母的序号，a是0，b是1...
		front_sum = x - last[char_num];
		back_sum = totnum - x;//得到的数就是x出发到最后一个元素的元素的总和（包括x自己）
		comb_sum = back_sum * front_sum;//组合数就是前和与后和相乘
		ans += comb_sum;
		last[char_num] = x; //把这个字母出现的地方记录下来 
	}
	printf("%lld",ans);
	return 0;
} </code>