yukicoder #557: 点対称

各桁に使える数は0,1,6,8,9のいずれかであってその特徴は以下のようになる。

                  先頭可    先頭不可

中心可      1 8           0

中心不可   6 9

先頭からceil(N/2)桁が決まると、残りfloor(N/2)桁は1通りに定まる。なので先頭からceil(N/2)桁だけ考える。場合分けする。

<1> Nが偶数の時

先頭の桁は1,8,6,9のいずれかの4通り。

続くceil(N/2)-1 = (N-2)/2 桁は 1,8,0,6,9の5通り。

よって

4*5^((N-2)/2) 通り

<2> Nが3以上の奇数の場合

先頭の桁は1,8,6,9のいずれかの4通り。

中心の桁は先頭ではないので1,8,0の3通り。

間の

ceil(N/2)-2 = (N-3)/2　桁は1,8,0,6,9の5通り。

よって

4*3*5^((N-3)/2) 通り

<3>Nが1桁の場合

1, 8の2通り