ちょっと思いつきにくそうなのでメモ。
長さ $N$ の数列 $A$ が与えられる。
$A$ の(連続でなくともよい)狭義単調増加列について、要素の XOR 和としてありうるものを列挙せよ。
$1 \le N \le 10^6$
$0 \le A_i \le 5000$
真っ先に思いつくのは dp[最後尾の要素]={現在のXOR和としてありうるものの集合} ですが、この時点でかなり正解から遠ざかっています。弱い制約版($N \le 10^5,A_i \le 500$) でも解けないでしょう。
key と value を入れ替えて dp[現在のXOR和]={最後尾の要素として考えられる最小のもの} とすると $O(NA_i)$ となり部分点は取れますが、この方針も満点から遠いです。
結論から言うと、正解のdpは
dp[単調増加列が次に要素として $x$ をとりうる]={現在のXOR和としてありうるものの集合}
です。ちょっと予定調和DP的ですね…
このDPにはいくつか嬉しい性質があり、その性質のおかげで $O(N+A_i^2)$ とできます。その性質は以下です。
- $A$ に $x$ が現れたとき、遷移を dp[$x$]からのみ行えばよい。遷移先は dp[$x+1$],dp[$x+2$],... であるが、後述の性質より、この数は減らせる。
- dp[$x$] から同じ遷移を何度も行う必要がないので、 dp[$x$] は queue のような形で保持して遷移を行い次第消していってもう二度と入れないとしてよい。
- dp[$x$] に $y$ が含まれたことがある場合、 dp[$x+1$],dp[$x+2$],... にも $y$ が含まれる。このため、これ以降の遷移を打ち切って良い。
これにより、「 dp[$x$] に $y$ が含まれる」という bool 配列を埋めていくイメージで、計算量の見積もりが $O(A_i^2(+N))$ とできます。
Submission #134156644 - Codeforces
嘘方針の罠がでかすぎる…
