子序列种类和

有同种类型的两题，一种是整数型的数组，一种是字符型的字符串
数组版：
有 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;
}