問題概要
長さ $N$ の数列 $A$ が与えられるので、(連続でなくともよい)部分列として取り出される方法が一意であるようなものを $\mod 998244353$ で数え上げよ。
$1 \le N \le 2 \times 10^5$
$1 \le A_i \le N$
最初 $dp[$ 要素 $x$ $]$ で $x$ がくるたびに預金を下ろすみたいな DP を考えたがそちらではうまくいかず。 $dp[$ 要素を取り出す位置 $i$ $]$ に方針を取り換える。
予め $arrow[i]=\{$ $A_i = A_j$ かつ $i<j$ なる最小の $j$ 、ただしそのような $j$ が存在しない場合は $N$ $\}$ を求めておく。
$i$ の昇順に $A_i$ を使うかどうかの DP を考える。
$dp[i]$ は、 $A_i$ を見る時点で 必ず「 $A_i$ までを見て、末尾として $A_i$ が採用された時の場合の数」が入っているようにする。
最初、 $dp[i]=1$ と初期化する。遷移は以下の通り。
- $dp[arrow[i]]=0$ とする。これは、 $A_i$ を使っていないのに $A_i$ を飛び越えて $A_{arrow[i]}$ を使うことを禁止するため。
- これにより、 $A_i$ と $A_j$ がこの順に隣接する区間で $A_j$ に起因する不都合がなくなる。
- $dp[i+1,arrow[i]]$ の範囲に $dp[i]$ を加算する。この範囲内の $j$ であれば $A_i$ の直後に $A_j$ を置くことが許される。
- これにより、 $A_i$ と $A_j$ がこの順に隣接する区間で $A_i$ に起因する不都合が生じない範囲での遷移が可能となる。
- $arrow[i]=N$ であれば $A_i$ で締めてよいので、答えに $dp[i]$ を加算する。
Submission #40576826 - AtCoder Regular Contest 125
むちゃくちゃ頭壊しながらガチャガチャしたらなんかACしてしまったので、整理するために記事化。でもまだ全然頭壊れてる。
