(より詳しい解説は後日ブログで公開します)

長さ \(n\) の 01 列で 1 が隣接しないもの個数 \(M_n\) は \(M_0 = 1,\, M_1 = 2,\, M_n = M_{n-1} + M_{n-2}\) を満たします．

実は，\(m = M_n\) が達成できます．これは，帰納的に

• \(n-1\) に対する模様の各行の末尾に 0 をつけたもの
• \(n-2\) に対する模様の各行の末尾に 01 をつけたもの

を上下反転などを行って適切に貼り合わせるとできることがわかります．

制約は \(N \le 26\) と同値です．\(M_n\) は指数的に増加するので，\(0, 1, \ldots, N\) に対する答えをすべて作っても計算量のオーダーは出力サイズのオーダーと同じです．