[ARC125D] Unique Subsequence

· · 题解

场切模拟赛 T2。

找出 A 中取出方案唯一的非空子序列 s 的数量。

考虑 DP，根据某巨佬口中“很典的方式”定义状态 f_i 表示以第 i 个数结尾的满足条件的非空子序列的个数。同时定义 pre_i 为 \max\limits_{j\in [1,i-1],a_j = a_i} j，即在 i 之前最后一个相同的数的下标，若没有则记为 0。

对于一个 i，pre_i>0，那么 f_i 就只能在 [pre_i,i-1] 中转移，因为从 [1,pre-1] 中转移的从 f_{pre_i} 也可以转移，所以代表取出方案并不唯一。

同理对于一组 i,j，j>i,pre_i>0，f_j 不能从 f_{pre_i} 转移，因为从 f_{pre_i} 转移过来的也能从 f_i 转移，所以也代表取出方案不唯一。

所以对于一个 i，可以从 \forall j\in[pre_i,i-1],j\ne pre_k(k\in[1,i-1]) 中转移过来，可以列出状态转移方程。

f_i=\begin{cases} \sum\limits_{j=pre_i}^{i-1} f_j\times [j\ne pre_k(k\in[1,i-1])] & (pre_i>0)\\ \sum\limits_{i=1}^{i-1} f_i\times [j\ne pre_k(k\in[1,i-1])]+1 & (pre_i=0) \end{cases}

考虑对区间求和进行优化，发现前缀和并不可行，所以我们使用树状数组，每次转移完后将 t_i 设为 f_i，t_{pre_i} 设为 0。查询 \sum\limits_{j=pre_i}^{i-1} t_j 即可。

f_i=\begin{cases} t(i-1,i)-t(pre_i-1,i) & (pre_i>0)\\ t(i-1,i)+1 & (pre_i=0) \end{cases} t(x,y)=\sum\limits_{i=1}^{x-1} f_i\times [i\ne pre_j(j\in[1,y-1])]

最后答案即 t(n,n)，也就是所有数字最后一个的 f 值的和。

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=2e5+10,MOD=998244353;
int n,a[MAXN],pre[MAXN],lst[MAXN];
long long f[MAXN],t[MAXN];
inline int lowbit(int x){return x&(-x);}
inline void change(int x,long long a)
{
    while(x<=n) t[x]+=a,t[x]%=MOD,x+=lowbit(x);
    return ;
}
inline long long query(int x)
{
    long long ans=0;
    while(x) ans+=t[x],ans%=MOD,x-=lowbit(x);
    return ans;
}
int main()
{
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n;
    for(register int i=1;i<=n;++i) cin>>a[i],pre[i]=lst[a[i]],lst[a[i]]=i;//记录 pre[i]
    for(register int i=1;i<=n;++i)
    {
        if(pre[i])
        {
            f[i]=(query(i-1)-query(pre[i]-1))%MOD;
            change(pre[i],-f[pre[i]]);//这里要转移完成后再更新
        }
        else f[i]=(query(i-1)+1)%MOD;
        change(i,f[i]);//将 i 号节点更新
    }
    cout<<(query(n)+MOD)%MOD<<'\n';return 0; 
}