\(k=0,1,2,\ldots ,2M\) について二項係数 \({}_{2M}\mathrm{C}_k\) を計算し、またその累積和を計算しておきます。ここから \(O(N+M)\) 時間で Piling Up の解を計算します。

出来上がるタワーについて、最初に入れておくべき

• 赤の最小個数が \(a\)
• 青の最小個数が \(b\)

であるものの個数を \(f(a,b)\) とします。

また、 \(g(a,b)\) を、初期状態において赤が \(a\) 個、青が \(b\) 個入っている場合に作れるタワーの種類数とします。

袋に残っているブロックの個数による制約を適用したグリッド上の経路数の数え上げに対応させます。

• 赤を取ることを左に移動すること、
• 青を取ることを上に移動すること

に対応させると、通行可能な領域の境界が右下がり \(45\) 度であるような場合の経路数に対応することがわかります。またこれは典型的な鏡像法によって、下図に示されるように二項係数の足し引きで計算できることがわかります。

この計算は累積和で効率化します。特に、 \(a+b=N\) を満たす範囲で \(g(a,b)\) の値を足し合わせるような計算が \(O(N+M)\) 時間でできます。

\(\displaystyle g(a,b)=\sum _ {0\leq p\leq a}\sum _ {0\leq q\leq b} f(p,q)\) によると、\(a+b=N\) を満たす範囲で \(g(a,b)\) の値を足し合わせたとき \(p+q\leq N\) において \(f(p,q)\) は \(N-p-q+1\) 回数えられています。この重複は \(a+b=N-1\) を満たす範囲で \(g(a,b)\) を計算して引くことによりちょうど除かれます。

解答例