题解：AT_arc125_d [ARC125D] Unique Subsequence

lovely_qiqi · 2025-11-06 18:32:26 · 题解

思路

比较 trick 的 DP。

直接设 dp_i 表示以 i 为结尾的方案数，lst_i 表示上一个 i 出现的位置。考虑什么时候会算重。发现和前面最近的一个数有关。我们发现对于 [1,i-1] 的子序列，加上 a_i 和 a_{lst_i} 显然是等效的。 于是它们肯定无法算进贡献里面。

所以方程就是：

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

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

代码

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

#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;
}