Description：

给一个长为 $n$ 的数列，设 $f[l][r]$ 表示子串 $a[l\dots r]$ 含有的本质不同子序列个数，求： $$ \sum_{i=1}^n\sum_{j=i}^nf[i][j] $$ $1\leqslant n\leqslant 10^5$

Solution：

设 $dp[i]$ 表示 $\begin{align}\sum_{k=1}^if[k][i]\end{align}$ ，那么转移为 $dp[i]=dp[i-1]\times2+2-(dp[last[a[i]]-1] + 1)$ 。

乘二的含义是原来每个都可以在最后加当前这个字符或者不加， $+2$ 代表 $f[i][i]$ ，但是这样会算重，因为在上一个这个数出现的位置有一些子序列已经被计算过了，所以要减掉，还有一个 $+1$ 代表当前这一位之前被计算过一次，这次重复了一遍又加了一个，但是没有在上一个容斥中删掉，所以要再减一。

感觉还是不是很懂啊。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

int a[MAXN];

int f[MAXN];

map<int,int> last;

#define MOD 998244353 

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= n;++i)

	{

		f[i] = (f[i - 1] * 2 % MOD + 2 - (last.find(a[i]) != last.end() ? f[last[a[i]] - 1] + 1 : 0) + MOD) % MOD;

		last[a[i]] = i;

	}

	int ans = 0;

	for(int i = 1;i <= n;++i)

	{

		ans = (ans + f[i]) % MOD;

	}

	cout << ans << endl;

	return 0;

}