ARC059 バイナリハック
考察
指定された文字を作る組み合わせを求める。
愚直な全探索だと3^5000通り
DPをしたくなりますが。0と1の扱いが難しい。状態数が増えます。
今回の問題だと文字数が同じであれば文字列を作る組み合わせは等しいので、0と1の区別をせずにまとめて計算をしてから2^(文字数)で割ってあげればよいという感じ。
ネックである01の処理をどうやりますかー？ってやつですね
dp[i][j] := i回目の操作で文字数jになる組み合わせ
で
if(j!=0)dp[i+1][j-1] += dp[i][j] else dp[i+1][j] += dp[i][j] dp[i+1][j+1] += 2*dp[i][l]
