なつやすみ 62日目
むむ
- 結局昨日の問題は解決した
昨日の問題というのは、f(S)=l(S)+conv(f,g)の形で求まるfをl,gから求めたいという問題 ここでconvはT|U=SかつT&U=0な集合(T,U)について積をとって足し合わせたもの
例えば、l={1,2,3,4}、g={0,5,6,7}とするとf={1,7,9,98}とかになる
f(01)=l(01)+f(01)*g(00)+f(00)*g(01)で、
f(11)=l(11)＋f(11)*g(00)+f(10)*g(01)+f(01)*g(10)+f(00)*g(11)になる
この例はg(00)＝0なおかげで自分自身を足さずに済んでるけど、g(00)が0でなくても求められると嬉しい*1
これは明らかO(3^N)のDPで求まるんだけど、これをO(N^2*2^N)で求めたくなる
subset convolutionを考えると、ranked zetaしたものを大文字で表せば
F=L+FGになる気がする これを変形してF=L/(1-G)としてもいけそうな気がする
実際これは大丈夫になる
つまり、gとlをranked zetaする→Gから1/(1-G)を求める→Lと各点積をとる→mobiusしてrankを下ろす とすれば良い
1/(1-G)は各点について形式的冪級数における逆元をx^|V|まで計算すればよく、これはN^2でできる*2 あと1は定数項の1なので注意(それはそう)
どのパートもO(N^2*2^N)になってうれしい
なぜ昨日失敗したか？
→mobiusのことを忘れて(01)と(10)を計算したときにx^2の項を計算していませんでした…… hosさんの資料に赤文字でx^|V|まで計算しなきゃダメですよって書いてあって涙
今後の課題
このままだと頂点v∈Sを含むT⊂S全体について集めるみたいなのができない
Connectivity 2のDPはこれで、困る どうやらlogとかexpとかを考えるとこれができるらしいけどこれ以上深掘りするのは体力的に厳しいのでまた今度 - yukicoder contest 316 面白かった
A：うむ
B：sumA(=コインの枚数)を固定する sumAを達成するように最小回数iを選んだ場合を考えると、それ以上の回数選んだ時の場合を全て覆っている
C：愚直実験を書いた 眺めると1の個数と1のいる座標の和が不変量とわかりこれが十分になると信じて書く
D：解けへん Manacherっぽいのが見えてうろうろしたりしてた
明日はManacherの勉強ですかね〜
