题解：AT_arc125_d [ARC125D] Unique Subsequence

思路

比较 trick 的 DP。

直接设

dp_i

表示以

i

为结尾的方案数，

lst_i

表示上一个

i

出现的位置。考虑什么时候会算重。发现和前面最近的一个数有关。我们发现对于

[1,i-1]

的子序列，加上

a_i

和

a_{lst_i}

显然是等效的。于是它们肯定无法算进贡献里面。

所以方程就是：

dp_i=\sum_{j=lst_i}^{i-1} dp_j

初值就是第一次出现的时候设为：

1+\sum_{j=1}^{j-1} dp_j

答案显然是所有 dp 值的和。注意你不应该重复算相同值的 dp 值。

代码

一个坑点是树状数组的写法，注意下标是

0

。

CPP

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int n,mod=998244353,tr[200010],a[200010],dp[200010],lst[200010];
int lowbit(int x){
	return x&(-x);
} 
void change(int x,int d){
	x++;
	for(int i=x;i<=1+n;i+=lowbit(i)){
		tr[i]=(tr[i]+d)%mod;
	}
}
int query(int x){
	x++;
	int tot=0;
	for(int i=x;i;i-=lowbit(i)) tot=(tot+tr[i])%mod;
	return tot;
}
signed main(){
	#define bnu cin
	#define hzy cout
	#define nkoj .tie(0)
	bnu nkoj;
	hzy nkoj;
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(lst[a[i]]==0) dp[i]=(1+query(i-1))%mod;
		else dp[i]=(query(i-1)-query(max(lst[a[i]]-1,0ll))+mod)%mod;
		change(i,dp[i]);
		change(lst[a[i]],-dp[lst[a[i]]]);
		dp[lst[a[i]]]=0;
		lst[a[i]]=i;
	} 
	cout<<(query(n)+mod)%mod;
	return 0;
}

题解：AT_arc125_d [ARC125D] Unique Subsequence

文章操作

思路

代码

相关推荐

评论

题解：AT_arc125_d [ARC125D] Unique Subsequence