这是本文档旧的修订版！

Atcoder Rugular Contest 125

比赛链接

D - Unique Subsequence

题意

给定一个长度为 $n$ 的序列 $A$，求该序列含有的独特的子序列个数(不包括空序列)。

其中，定义独特的子序列为序列 $A$ 的所有子序列构成的可重集中出现次数等于 $1$ 的子序列。

题解

设 $\text{dp}(i)$ 为以位置 $i$ 结尾的独特子序列个数。

考虑从 $1\sim n$ 动态维护每个 $\text{dp}(i)$。假设当前位置为 $i$，求出最大的 $j$ 满足 $j\lt i\And a_i=a_j$。

对于所有终止位置小于 $j$ 的独特子序列，加上 $a_i$ 显然不构成独特子序列，因为有 $a_j,a_i$ 两种选择。

对于所有终止位置 $\in [j,i)$ 的独特子序列，加上 $a_i$ 还是独特子序列，因为只有 $a_i$ 一种选择。于是有 $\text{dp}(i)=\sum_{k=j}^{i-1} \text{dp}(k)$。

同时，加入 $a_i$ 后所有前面以 $a_i$ 结尾的独特子序列都不再独特，因此有 $(j\lt i\And a_i=a_j)\to (\text{dp}(j)=0)$。

考虑树状数组加速上述操作，时间复杂度 $O\left(n\log n\right)$。最后答案即为所有 $\text{dp}$ 值相加。

查看代码

const int MAXN=2e5+5,mod=998244353;
#define lowbit(x) ((x)&(-x))
int c[MAXN];
void add(int pos,int v){
	while(pos<MAXN){
		c[pos]=(c[pos]+v)%mod;
		pos+=lowbit(pos);
	}
}
int query(int pos){
	int ans=0;
	while(pos){
		ans=(ans+c[pos])%mod;
		pos-=lowbit(pos);
	}
	return ans;
}
int query(int l,int r){
	return (query(r)+mod-query(l-1))%mod;
}
int a[MAXN],lst[MAXN],pre[MAXN],dp[MAXN];
int main()
{
	int n=read_int();
	_rep(i,1,n){
		a[i]=read_int();
		pre[i]=lst[a[i]];
		lst[a[i]]=i;
	}
	int ans=0;
	_rep(i,1,n){
		if(pre[i]){
			dp[i]=query(pre[i],i-1);
			add(pre[i],mod-dp[pre[i]]);
			dp[pre[i]]=0;
		}
		else
		dp[i]=(query(1,i-1)+1)%mod;
		add(i,dp[i]);
	}
	_rep(i,1,n)
	ans=(ans+dp[i])%mod;
	enter(ans);
	return 0;
}

CVBB ACM Team

目录

Atcoder Rugular Contest 125

D - Unique Subsequence

题意

题解

CVBB ACM Team

用户工具

站点工具

目录

Atcoder Rugular Contest 125

D - Unique Subsequence

题意

题解

页面工具