AGC 12 C - Tautonym Puzzle ( Binary Enumeration )

C: Tautonym Puzzle - AtCoder Grand Contest 012 | AtCoder

題意：
要求構造一個字串 S，使得 S 有洽 N 個偶數長度 ( ≥ 2 ) 的子序列，使得子序列前半等於子序列後半。

資料規模：
1≦|s|≦200
s は 1 から 100 までの整数で表される 100 種類の文字のみからなる。
s の 2|s| 個ある部分列のうち、良い文字列であるようなものは N 個ある。

解法：
賽中只有看出來大概是 *2 / +1 的解法，但沒想出來怎麼對應... 功力不足再接再厲( ?
構造的方法其實很簡單，是這樣的：
若 A + B 有 X 種方法，考慮一個還未出現的字符 $，那麼只要 A + $ + B + $ 就有 2 * X 種方法，A + $ + $ + B 就有 X + 1 種方法。
最後一個細節要注意的是，這個構造方式會讓空字串也會被算入，這裡只要將輸入的 N 增加 1 就可以。

時間 / 空間複雜度：
O( lg N )

from collections import deque

N = int( input() ) + 1 # + 1 for empty sequence

hi = 0
while 1 << hi + 1 <= N:
  hi += 1
hi -= 1

ans_A = deque()
ans_B = deque()
ptr = 1
for i in range( hi, -1, -1 ):
  ans_A.append( ptr )
  ans_B.append( ptr )
  ptr += 1
  if N >> i & 1:
    ans_A.append( ptr )
    ans_B.appendleft( ptr )
    ptr += 1

print( len( ans_A ) * 2 )
# print( * ( ans_A + ans_B ) )
for i in range( len( ans_A ) ):
  print( ans_A[ i ], end = ' ' )
for i in range( len( ans_B ) ):
  print( ans_B[ i ], end = ' \n'[ i + 1 == len( ans_B ) ] )