B - L Partition Editorial
by 
maspy
ヒント → https://atcoder.jp/contests/arc190/editorial/11715
[1] 問題の言い換え
レベル \(N\) の L 型の置き方は，先頭または末尾の行・先頭または末尾の列を占有する高々 \(4\) 通りしかありません．「レベル \(k\) 以下の L 型が置かれるマス」は縦横の長さが \(k\) の正方形であることが \(k=N,N-1,\ldots\) の順に分かります．このことを整理して L 型への分割を言い換えると，次のようになります．
\(L\) 型への分割は，区間の列 \([1,N]=I_N\supsetneq \cdots \supsetneq I_1\) および \([1,N]=J_N\supsetneq \cdots \supsetneq J_1\) をひとつずつ選ぶことと対応する（\(I_i,J_i\) は連続する \(i\) 個の整数からなる区間）．このような区間の選び方に対して，\(I_k\times J_k\) にレベル \(k\) 以下の L 型が置かれる．
求めるべきは \((a,b)\) がレベル \(k\) の L 型に含まれるような分割の数え上げですが，代わりに「\((a,b)\) がレベル \(k\) 以下の L 型に含まれるような分割」を数えてから差分をとることにします．次の問題が解ければよいことになります：
区間の列 \([1,N]=I_N\supsetneq \cdots \supsetneq I_1\) および \([1,N]=J_N\supsetneq \cdots \supsetneq J_1\) の組であって，\((a,b)\in I_k\times J_k\) を満たすものの個数を求めよ（ただし \(I_i,J_i\) は連続する \(i\) 個の整数からなる区間）．
これはもちろん縦方向・横方向に独立な数え上げの積として計算できるので，次が解ければよいです．
区間の列 \([1,N]=I_N\supsetneq \cdots \supsetneq I_1\) であって，\(a\in I_k\) を満たすものの個数を求めよ（ただし \(I_i\) は連続する \(i\) 個の整数からなる区間）．
[2] 数え上げ
\(I_N\supsetneq \cdots \supsetneq I_k\ni a\) を満たす区間の列の個数を \(c_k\) と書くことにします．
このような区間の列は \(I_N\supsetneq \cdots \supsetneq I_{k+1}\ni a\) も満たしているので，\(c_k\) は \(2c_{k+1}\) から次を満たす区間の列の個数を引いたものです．
- \(I_N\supsetneq \cdots \supsetneq I_{k+1}\supsetneq I_k\) かつ \(a\in I_{k+1}\) かつ \(a\notin I_k\).
すると，\(c_k\) は \(2c_{k+1}\) から適当な二項係数を引いたものとして計算できることが分かります．したがって \(c_N,\ldots,c_1\) はすべてあわせて \(O(N)\) 時間で計算できます．
なおこの部分の計算は，\(\sum_{a\leq i\leq b}\binom{k}{i}\) を \(k=1,2,\ldots,N\) に対して計算するというタイプの問題に言い換えて導出することもできます．
posted:
last update: