ABC115D

考えのまとめ。実装はまだなので、TLEが出るかもしれないけれど共有。

とりあえずN＝N_maxのときのバーガーの層の数を求めてみる。これは漸化式を解くだけ。レベルNバーガーの層の数をL(N)とおくと

L(N_max)＝2^(N_max+2)-3=2^52-3

これをすべて求めるのはO(10^8)を大きく超えるので、そのまま求めるのは不可能

問題文よりバーガーには対称性がある。その半分はB（レベルN-1バーガー）Pという形をしている。このレベルN-1バーガーには同様に対称性が適応出来る。

これらより、tmp_x = Xとして

i tmp_x>=L(N)/2のとき
ansにレベルNバーガーのPの数+1をaddしてレベルN-1バーガーに対して同様の処理を行う。このときtmp_x-=L(N/2)とする

ii tmp_x<L(N)/2のとき
ansに何もせず、レベルN-1バーガーに同様の処理を行う。このときtmp_x-=1とする

iii N=0のとき
tmp_x=0ならば0、tmp_x=1ならば1をansに足す。

でいけるはず。