526.1
ちょっと変則な時間だった。
250
見てない。
500
見てない。
1000
長さ50程度の0か1からなる文字列が50個ほど与えられるので、それらから一個ランダムに選ぶ操作をK回行ってできる文字列に、長さ500程度の文字列が何回出現するか期待値を答えよ、という問題。
期待値なのでDPで、Kがとっても大きいから行列乗算をべき乗でやって高速化、という脊髄が悪さして、きっと0か1からなる文字列だから、状態数が500よりも小さく圧縮できるんだろう、と思い込んでコーディング開始。結局そんなことはなくって、別の解法で通すらしい...。
0と1からなる文字列だから、状態遷移はそんなに複雑にならなくて、そのうちループするとかどうとか、そういう感じみたい...？
