有同种类型的两题，一种是整数型的数组，一种是字符型的字符串
数组版：
有 n 个数字 a1、a2、a3...an，求子序列和
如：
4
1 2 1 3
子序列有
{1}，{1，2}，{1，2，1}，{1，2，1，3}
{2}，{2，1}，{2，1，3}
{1}，{1，3}
{3}
种类和{1+2+2+3}+{1+2+3}+{1+2}+{1}=18
思路：直接求单个数字的贡献，直接上代码吧
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
#define pii pair<int,int>
const int maxn=10005;
int a[maxn];
int vis[maxn];
int main(){
ios::sync_with_stdio(false);//加速的
memset(vis,0,sizeof vis);
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
int ans=0;
for(int i=1;i<=n;i++){
ans+=(i-vis[a[i]])*(n-i+1);
vis[a[i]]=i;//标记每次出现后的位置
}
cout<<ans<<endl;
return 0;
}
字符串原理一样，直接上例子和代码：
输入
abac
输出
18
代码
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
#define pii pair<int,int>
const int maxn=10005;
int vis[maxn];
char s[maxn];
int main(){
ios::sync_with_stdio(false);//加速的
memset(vis,0,sizeof vis);
cin>>s+1;
int n=strlen(s+1),ans=0;
for(int i=1;i<=n;i++){
ans+=(i-vis[s[i]-'a'])*(n-i+1);
vis[s[i]-'a']=i;//标记每次出现后的位置
}
cout<<ans<<endl;
return 0;
}
