【今日の精進】ARC125D - Unique Subsequence

毎日格上の問題を倒すやつの83日目です。

問題リンク

atcoder.jp

問題概要

から連続とは限らない部分列を取り出す方法であって、取り出し方が一意に定まるものの個数を求めてね。

解法

• 番目の要素を必ず選ぶ通り数

とします。そこで、遷移を考えましょう。

ある数が動かせてはいけないので、 と同じ数があるところまでの和と、その間で 種類以上あるものは一番後のものを考えていい感じにやれば良いです。

更新と区間和取得のできるものがほしくなりますが、まあどうとでもなります。

提出コード

class BinaryIndexedTree():
    def __init__(self,default=0):
        self.size=0
        if type(default)==int:
            self.size=default
        else:
            self.size=len(default)
        self.bit=[0 for i in range(self.size+1)]
        self.stan=[0 for i in range(self.size)]
        if type(default)!=int:
            for i,j in enumerate(default):
                self[i]=j
    
    def __setitem__(self,pos,val):
        add=val-self.stan[pos]
        self.stan[pos]=val
        pos+=1
        while pos<=self.size:
            self.bit[pos]+=add
            pos+=pos&(-pos)
    
    def __getitem__(self,pos):
        if type(pos)==int:
            return self.stan[pos]
        else:
            left=pos.start
            if left==None:
                left=0
            right=pos.stop
            if right==None:
                right=self.size
            return self._sum0(right-1)-self._sum0(left-1)
        
    def _sum0(self,right):
        pos=right+1
        ret=0
        while pos>0:
            ret+=self.bit[pos]
            pos-=pos&(-pos)
        return ret

MOD=998244353
N=int(input())
A=list(map(int,input().split()))
last=[-1]*(N+1)
dp=BinaryIndexedTree(N+1)
dp[0]=1
for i in range(N):
    dp[i+1]=dp[last[A[i]]+1:i+1]
    dp[i+1]%=MOD
    if last[A[i]]!=-1:
        dp[last[A[i]]+1]=0
    last[A[i]]=i
print(dp[1:]%MOD)

Submission #48440243 - AtCoder Regular Contest 125

感想

素直にDPできなかったなぁ