客 \(i\) が入店時に名前を書いたら \(C_i = 0\)、そうでないなら \(C_i = 1\) と定義します。ある最終的な順列 \(P\) について、二つの（上述のような）列 \(C1, C2\) がともに \(P\) を生成したとします。このとき、\(C_i = \min(C1_i, C2_i)\) で定義される列 \(C\) も \(P\) を生成することを示しましょう。\(C_1\) と \(C_2\) で値が異なる最初の位置を \(i\) とし、例えば \(C1_i = 0, C2_i = 1\) であるとします。このとき、\(C2_i\) を \(0\) に変えても明らかに順列は変わりません。時刻 \(A_i\) と \(B_i\) の間に書き込みはないはずだからです（そうでないと、\(C1\) と \(C2\) に対する順列が一致しません）。この調子で進めると、双方の列が \(C\) と一致します。

ここから、生成され得る各順列 \(P\) に対し、それを生成する列 \(C\) であって、どの要素 \(C_i\) を \(1\) から \(0\) に変えても生成される順列が変わるようなものがただ一つ存在することが従います。つまり、\(C_i = 1\) であるような各 \(i\) について、時刻 \(A_i\) と \(B_i\) の間に客 \(i\) 以外の書き込みが一回以上あるような列です。この条件を満たす列の個数が答えとなります。

このような列の個数は、例えば包除原理を使って数えられます。\(C_i = 1\) であって区間 \([A_i, B_i]\) に他の書き込みがないとき、\(i\) に「問題」があるということにします。問題がある位置の集合を列挙しましょう。

\(B_j > A_i\) であるような最小の \(j\) を \(L_i\)、\(A_j < B_i\) であるような最大の \(j\) を \(R_i\) とします。もし \(i\) に問題があるとすれば、\(C_{L_i} = \ldots = C_{i - 1} = 0, C_i = \ldots = C_{R_i} = 1\) でなければなりません。ここで、\(R_i \geq L_j\) であるような二つの位置 \(i < j\) について、 \(i\) と \(j\) に同時に問題があるということは起こり得ないことに注意します。よって、包除原理で列挙した集合のうち、対応する列が \(0\) 個でないものは、交わりを持たない区間 \([L_i, R_i]\) の集まりに対応し、その「重み」は \(2^x (-1)^y\) です。ここで、\(x\) は集合内のどの区間でも覆われていない位置の個数、\(y\) は集合内の区間の個数です。これらの総和は、動的計画法で容易に \(O(N)\) 時間で計算できます。