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

0 か 1 を挿入する操作は，結果の文字列が同じものを区別しないとき，以下でちょうど尽くされます：

• 先頭に 1 を挿入する
• 0 を 01 で置き換える
• 1 を 01 で置き換える
• 末尾に 0 を挿入する

このことから，条件を満たす \((t_0, t_1, \ldots, t_N)\) は，\((0, 1, \ldots, N)\) の順列 \((p_0, p_1, \ldots, p_N)\) であって，\(t_N\) の \(j\) 文字目が 0 のとき \(p_{j-1} < p_j\)，1 のとき \(p_{j-1} > p_j\) であるようなものに一対一対応することが証明できます．よって，順列の数え上げに帰着されました．

\(S\) の ? で区切られた各部分は独立に考えて多項係数をかければよいです．

以下 \(S\) が ? を含まないとします．1 の条件に包除原理を用いると，1 の位置を \(j_1 < \cdots < j_m\) 文字目として，\(j_0 = 0\)，\(j_{m+1} = N + 1\) とおいて，答えは \(\sum_{0 = k_0 < k_1 < \cdots < k_l < k_{l+1} = m + 1} (-1)^{m-l} (N + 1)! / ((j_{k_1} - j_{k_0})! (j_{k_2} - j_{k_1})! \cdots (j_{k_{l+1}} - j_{k_l})!)\) となります．これは分割統治と FFT によって \(O(N (\log N)^2)\) 時間で計算できます．