ARC125D

题意

给定长度为 \(n\) 的序列中，求其中只出现过一次的非空子序列的个数，对 \(998244353\) 取模。

题解

不难发现，一个只出现过一次的子序列合法的充分必要条件是：

头部元素 \(a_i\) 是原序列中下标最小的（即最左边的）值为 \(a_i\) 的元素
由对称性，该子序列最后一个元素 \(a_i\) 是原序列中最后一个出现的值为 \(a_i\) 的元素
子序列中任意相邻两元素在原序列中，不妨设它们的下标分别是 \(l,r\) 则 \(\forall a_i,l<i<r\) ，\(a_i\neq a_l\) 且 \(a_i\neq a_r\)

这些条件可以举一些例子验证。

为了简化程序，我们可以为原序列设首尾两个哨兵，

具体地，令 \(a_0=max\{a_i\}+1, a_{n+1}=max\{a_i\}+2,1\leq i\leq n\)

这样 \(a_0\) 与 \(a_{n+1}\) 就和原序列任意元素不相同了，

接着，我们求以 \(a_0\) 为头，\(a_{n+1}\) 为尾的合法子序列个数，

我们就不必考虑条件 1 和条件 2 了。

然后就可以 dp 了，

记 \(f_i\) 为以 \(a_i\) 结尾的合法子序列个数，\(lst_i\) 为值为 \(i\) 的元素目前为止最后出现的位置，则

\(f_0=1\)

\(f_i=\sum\limits_{j=lst_{a_i}}^{i-1} f_j \times [j==lst_{a_j}] (i\neq 0)\)

实际我们需要不断维护 \(lst_{a_i}\) 每次顺带把 \(f_{lst_{a_i}}\) (更新前的) 置为 0 ，这样转移时的求和就是区间求和了。

再加上单点修改，可以直接树状数组维护。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
typedef long long ll;
const int mod=998244353;
int a[N],n,c[N],f[N],lst[N],m;
inline int lowbit(int x){return x&-x;}
void add(int x,int val){
	x++; //由于要用到0这个下标，树状数组中把所有下标偏移1 
	for(;x<=n+1;x+=lowbit(x)) c[x]=((c[x]+val)%mod+mod)%mod;
}
int ask(int x){
	x++; //同上 
	int ret=0;
	for(;x;x-=lowbit(x)) ret=((ret+c[x])%mod+mod)%mod;
	return ret;
}

int main(){
	
	cin>>n;
	for(int i=1; i<=n; i++){
		scanf("%d",&a[i]);
		m=max(m,a[i]);
	}
	a[0]=m+1,a[n+1]=m+2; //设哨兵 
	
	f[0]=1; add(0,1);
	for(int i=1; i<=n+1; i++){
		f[i]=(ask(i-1)-ask(lst[a[i]]-1)+mod)%mod;
		if(lst[a[i]]) add(lst[a[i]],-f[lst[a[i]]]);
		add(i,f[i]);
		lst[a[i]]=i;
	}
	
	cout<<(f[n+1]-1+mod)%mod; //子序列不能空，所以减1 
	
	return 0;
}