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

\(A\) の元を見やすさのため \(a = (a_0, l_0, r_0, \ldots, l_{N-1}, r_{N-1})\) と書きます．

区間 \([l_0, r_0], \ldots, [l_{N-1}, r_{N-1}]\) のうち，後ろ \(k\) 個の共通部分は空でないが後ろ \(k+1\) 個の共通部分は空である，というような \(k\) がとれたとします．後ろ \(k\) 個の共通部分を \([l, r]\) とおきます．さらに \(l_{N-k-1} < r_{N-k-1} < l < r\) を仮定すると，\(f(a) = l\) となります (\(l < r < l_{N-k-1} < r_{N-k-1}\) のときは \(f(a) = r\) で，以降の議論も同様です)．\(k, l\) を固定すると \(a\) は \(l! (2N-l)! k 2^{-(N-k)} \displaystyle\binom{2N-2k-1}{l-k-1}\) 通りと数えられます．

ここで，\(f_{l,s,t} = \displaystyle\sum_{k=1}^{N-1} k^s 2^k \binom{2N-2k-t}{l-k-1}\) (\(s, t \in \{0, 1\}\)) とおくと， \(f_{l,*,*}\) たちは \(f_{l+1,*,*}\) たちから (二項係数計算の準備のもと) \(O(1)\) 時間で計算できることがわかります．

\(k\) がとれない場合，すなわち \(N\) 個の区間が共通部分を持つときは， \(f(a) = N\) となることがわかります． そのような \(a\) は \((2N+1) (N!)^2\) 通りです．

合計で \(O(N)\) 時間で \(f(a) = 0, \ldots, 2N\) それぞれの個数がわかります．