dpの区間クエリみたいなやつ

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

DDCCのD問題の発展問題情報（K） opencup.ru/files/oci/gp10…

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

長さ10^6の文字種52の文字列Sが与えられ、以下のオンラインクエリが10^6個来る。 ・区間[l,r]に含まれる相異なる部分列は何通りあるか O((N+Q)*52)で解いてください。 解説：drive.google.com/file/d/1plwnwr…

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

補足：部分文字列じゃなくて部分列です。subsequenceです。abc->acみたいなやつ。あと、取り出す場所が違っても文字列として一緒なら１個として数える。（じゃないと自明）

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

この問題すごい。この計算量でギリギリ解けるのびっくりした。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

昔見たときは、逆行列使えばlog取れるんだ〜くらいしか理解してなかったけど、これもっと強力で汎用的だな。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

dpの遷移がK次正方行列で表せてかつ逆行列があるとき、O(N*K^3+QK) さらに、遷移がO(N)ならO(N*K^2+QK)に、遷移がO(1)ならO((N+Q)*K)にできる(条件が正確かは自信がない)

タッパーをオーブンで焼かない @DEGwer3456

@snuke_ 遷移 O(1) ってどういう状況ですか

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

@DEGwer3456 行列とかを忘れてdpした時の遷移です。(値が変わらないところは使い回す)

sigma @sigma425

@DEGwer3456 @snuke_ a_k = (k==x[i] ? 1 : a_k) とか

タッパーをオーブンで焼かない @DEGwer3456

@snuke_ 結局累積積全部持っておかないといけないから永続配列とか必要になりませんか

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

@DEGwer3456 うん。ただそこでlogは付かないようにできると思う。(例えばvectorへのポインタをコピーするだけなら一回の遷移でO(K))

タッパーをオーブンで焼かない @DEGwer3456

@snuke_ あー配列サイズは K^2 だから sqrt でやれば充分なのか

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

@cagypaper 戻すDPは逆行列掛けてるだけって話だと思う