1.前言
十几天没动了，好不容易找到时间去锻炼一下，结果就错过了比赛，而且自己应该能加大把 rating 的。 /ts
2.题解
这道题很像这道题，所以证明就不写了。
状态定义：
假设现在枚举到了 \(i\), 令 \(dp[j]\) 表示子序列以 \(a[j]\) 结尾的方案数。
状态转移：
1. \(\forall j \in [1,i),a[j] \neq a[i]\)
\(dp[i] = (\sum_{k = 1}^{i - 1}dp[k]) + 1\)
2. \(\exists j \in [1, i), a[j] = a[i]\)
令 \(p = \max j (j \in [1, i), a[j] == a[i])\)
则 \(dp[i] = \sum_{p}^{i - 1}{dp[k]} (\forall {q < k}, a[q] \neq a[k])\)
证明：略，参考这篇题解
实现：
发现式子是一个 \(O (n ^ 2)\) 的，我们考虑用数据结构优化。
如果发现 \(\exists {j < i},a[j] == a[i]\)，就将 \(res -= dp[j]，dp[j] = 0\)，正确性显然，就不证明了。
参考代码（注释掉的是\(O (n ^ 2)\)暴力）
#include <set>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define PII pair <int, int>
#define LL long long
#define ULL unsigned long long
template <typename T> void read (T &x) { x = 0; T f = 1;char tem = getchar ();while (tem < ‘0‘ || tem > ‘9‘) {if (tem == ‘-‘) f = -1;tem = getchar ();}while (tem >= ‘0‘ && tem <= ‘9‘) {x = (x << 1) + (x << 3) + tem - ‘0‘;tem = getchar ();}x *= f; return; }
template <typename T> void write (T x) { if (x < 0) {x = -x;putchar (‘-‘);}if (x > 9) write (x / 10);putchar (x % 10 + ‘0‘); }
template <typename T> void print (T x, char ch) { write (x); putchar (ch); }
template <typename T> T Max (T x, T y) { return x > y ? x : y; }
template <typename T> T Min (T x, T y) { return x < y ? x : y; }
template <typename T> T Abs (T x) { return x > 0 ? x : -x; }
const int Maxn = 2 * 1e5;
const LL Mod = 998244353;
int n, a[Maxn + 5];
int idx[Maxn + 5];
LL dp[Maxn + 5];
LL BIT[Maxn + 5];
int lowbit (int x) { return x & -x; }
void Update (int Index, LL x) {
for (int i = Index; i <= Maxn; i += lowbit (i))
BIT[i] = (BIT[i] + x + Mod) % Mod;
}
LL Query (int Index) {
LL res = 0;
for (int i = Index; i >= 1; i -= lowbit (i))
res = (res + BIT[i] + Mod) % Mod;
return res;
}
LL Calc (int l, int r) {
return (Query (r) - Query (l - 1) + Mod) % Mod;
}
int main () {
read (n);
for (int i = 1; i <= n; i++) {
read (a[i]);
}
LL res = 0;
for (int i = 1; i <= n; i++) {
if (idx[a[i]] == 0) {
/*
dp[i] = pre[i - 1] + 1;
*/
dp[i] = Query (i - 1) + 1;
}
else {
/*
dp[i] = (pre[i - 1] - pre[idx[a[i]] - 1] + Mod) % Mod;
res = (res - dp[idx[a[i]]] + Mod) % Mod;
for (int j = idx[a[i]]; j < i; j++) {
pre[j] -= dp[idx[a[i]]];
pre[j] = (pre[j] + Mod) % Mod;
}
*/
dp[i] = Calc (idx[a[i]], i - 1);
res = (res - dp[idx[a[i]]] + Mod) % Mod;
Update (idx[a[i]], -dp[idx[a[i]]]);
}
/*
idx[a[i]] = i;
pre[i] = pre[i - 1] + dp[i];
res += dp[i];
res %= Mod; dp[i] %= Mod; pre[i] %= Mod;
*/
idx[a[i]] = i;
Update (i, dp[i]);
res += dp[i];
res %= Mod;
}
write (res);
return 0;
}