はじめに部分点方針を考えます。問題文を読み替えると、\((A_i,B_i)\) を次の操作を用いて確定させる方法を数える問題になります。

• はじめに \(A_i, B_i\) を全て \(-1\) で初期化する。
• \(t=0,1,\dots,T-1\) について次の一連の操作を行う。
  1. \(A_i =-1\) である要素をいくつか選び \(A_i \gets t\) とする。
  2. \(A_i \neq -1, B_i = -1\) である要素をいくつか選び \(B_i \gets t+1\) とする。
• 操作の過程において \(A_i \neq -1, B_i=-1\) である \(i\) が常に \(2\) 個以下であり(これが 2 個の録画機で録画できる必要十分条件)、かつ最終的に \(-1\) が存在しない \(A_i, B_i\) の組が条件を満たす。

上記のように言い換えると、\(dp[n][m]\) : \(n\) 個の \(A_i\) を確定して、\(A_i \neq -1, B_i=-1\) である \(i\) が \(m\) 個である通り数、として DP をすることで 2 乗時間でこの問題を解くことが出来ます。

これを母関数を用いて高速化します。詳細は省略しますが、いくらかの考察により、指数型母関数を用いると

\[ V = \left( \begin{matrix} 1 & x & \frac{x^2}{2} \\ 0 & 1 & x \\ 0 & 0 & 1 \\ \end{matrix} \right), W = \left( \begin{matrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 2 & 1 \\ \end{matrix} \right) \]

と置いた時の

\[\left[ \frac{x^N}{N!} \right]{(VW)^T}_{1,1}\]

が答えになることがわかります。上式の値を \(1 \leq T \leq U\) の範囲で列挙することは ARC202 で解説した特殊な分割統治 で \(\mathrm{O}(U \log^2 U)\) でできるので、問題を解くことが出来ます。