ARC 059 F バイナリハック について
まーすさんのブログにいちゃもんを付けたら（ごめんなさい）おもしろい話になったので反省も兼ねてブログにメモします。
この問題のsが空文字列である場合の答えa_Nがどんな数列になるかという話をしていました。
つまりこれの途中で出てきたけど結局使わなかったやつです。
dpをするとどうなるか
まず、キーを押す操作を逆から考えます。こうすると、削除は何回でもできるけど入力は今までに削除した回数以上はできないというルールになります。
i回入力してj回削除をする方法の数をi行j列に書いたdpテーブルを考えます。左上に1を書いてから、上の数の2倍+左の数をどんどん書いていけばok
この表でn回キーを押した状態は斜めに並んでいます。なので、求める数はこの表を斜めに足し上げた数です（赤で書いてあるやつ）。この数列はOEISすると出てきます。
漸化式
この数列をよく見ると、nが奇数の時a_{n+1}=a_nになってます。なぜそうなるのかを考えてみると、
こんな感じで、それぞれの数について左側に普通に足したものと、下に2倍して足したものが足されるからだと分かります。だからnが奇数ならこれは絶対成り立ちます。つまり、a_{2n}=3a{2n-1}です。
偶数の時はどうかというと、左下の数の下に数字を書くことが無い（入力する数の方が多くなるから）ため、この法則が成り立ちません。3倍しただけだと、左下の数の2倍だけ本来の数よりも大きくなってしまうので、その分を引いてやる必要が出てきます。
左下の数というのは、削除と入力を同じ回数する場合の数でした。削除の数は入力の数より少なくては行けないので、これは括弧の付け方みたいなもので、ほぼカタラン数です。ぴったりカタラン数ではないのは、この問題では入力の方法が2通りあるからで、入力の数だけ2を掛ければよいです。つまり、合計で2n回キーを押した時の左下は、2^nc_nとなります（c_nはカタラン数のn項目）。つまり、a_{2n+1}=3a_{2n}-2^{n+1}c_nです。
数式をきれいにしたいので後で調べて直します
