数列 \(a\) をグリッド上のパスに対応させる． \(f(a)\) の \(k\) 番目 \(> h\) という条件を考えてみる．

グリッドに斜め線を引いて，その線の上でパスが右に移動した回数が \(k\) 回以上なら OK，といった条件になる．

解法に必要な補題を紹介する．

補題：\(N \times N\) グリッドを考えて，\((0,0)\to(N,N)\) へのパスを考える． 対角線 \((0,0)\to(N,N)\) の上で \(k\) 回右に移動するようなパスの個数を \(c(N,k)\) とおく． このとき，\(c(N,0)=c(N,1)=\cdots=c(N,N)\) になる．

天下り的に巧妙な全単射を作ることもできるが，ここでは母関数による証明を行う．

\((0,0)\) からスタートし，初めて対角線に触れるのが \((n,n)\) であるような経路の数を考える． 対角線の下側を通るような経路に対応する母関数は \((1-\sqrt{1-4x})/2\) になる．これはカタラン数の母関数からわかる．上側も同じ． ここで，対角線の上で右に移動した回数に変数 \(y\) を対応させることで，\(2\) 変数多項式にしてみる． すると，対角線の下側は \((1-\sqrt{1-4x})/2\), 上側は \((1-\sqrt{1-4xy})/2\) になる． これを元に \(f(x,y)=\sum c(N,k) x^N y^k\) を計算してみると

\[ \begin{aligned} f(x,y) &= \frac{1}{1-(1-\sqrt{1-4x})/2- (1-\sqrt{1-4xy})/2} \\ &= \frac{2}{\sqrt{1-4x}+\sqrt{1-4xy}} \\ &= \frac{2(-\sqrt{1-4x}+\sqrt{1-4xy})}{-(1-4x)+(1-4xy)} \\ &= \frac{1}{1-y}\left(\frac{1-\sqrt{1-4x}}{2x} +\frac{1-\sqrt{1-4xy}}{2x} \right)\\ \end{aligned} \]

となる．ここから \([x^N]f(x,y)\) について考えると，\(y^0,y^1,\cdots,y^N\) の係数がすべて等しいことがわかる．よって示された．

この事実を元の問題に応用してみる．

\((0,0) \to (N,M)\) のパスが，直線 \(y=x+h\) の上で何回右に移動したか，を考えたい．

\(0 \leq h \leq M-N\) のケースを考える． 直線 \(y=x+h\) にパスが初めて触れる点 \((p,p+h)\) と最後に触れる点\((q,q+h)\) を固定する． \(p-q\) 間で斜め線の上を通る移動の回数は \([0,q-p]\) の範囲で一定であることが補題からわかる．

\((q,q+h)\) を通ったあとは常に斜め線の上を通ることになるので，結局，斜め線の上側を通る回数は \([n-q,n-p]\) の範囲で均等に分布する．

\(p,q\) を固定したら \(ans[n-q,n-p]\) に \(v(p,q)\) (\(=p\) で初めて斜め線に触れて \(q\) で最後に斜め線に触れる方法のうち，\(p,q\) 間で斜め線の上側に出ないもの)を足す，という操作になるが，ここで累積和の考え方を使う．\(ans\) の隣接 \(2\) 項の差を \(dif\) と表すことにすると，\(dif[n-q]\mathrel{+}=v(p,q), dif[n-p+1]\mathrel{-}=v(p,q)\) という操作になる．

ここで \(q\) を固定したまま \(p\) を動かしてみると，\(\sum_{0 \leq p \leq q} v(p,q)\) が求めたいことになるが，これは単に，\((q,q+h)\) までは斜め線を超えず，その後は斜め線に触れないパスの数になる． これはカタラン数の計算と同じような手法 (鏡像法) を用いれば，二項係数の積（の定数個の和）で書ける．

ここで更に \(h\) を動かしてみる． すると求めたい和は，以下のような形(あるいは少しだけ添字がずれたもの)になる．

\[ \sum_{0 \leq h \leq M-N} {2q+h \choose q} \times {N+M-h-2q \choose N-q} \]

これをすべての \(q\) について求めるのが目標． これは \(q\) を \(0 \to N\) と動かしていくと全体で \(O(N+M)\) でできる． （\(q\) を \(1\) 増やしたときの値の変化を考えると定数回の計算で処理できる．）

今は \(q\) について考えていたが，\(p\) についても全く同様にできる． これで \(0 \leq h \leq M-N\) のケースは処理できた．

\(M-N<h\) のケースはより簡単に処理できる． 先ほどと同様に，直線 \(y=x+h\) に最初と最後に触れる場所を \(p,q\) とおく． 今度は \(q-p\) で分類してパスを数え上げれば良い． \(q-p\) を固定して \(h\) を動かすと，二項係数の和や差の形になる． これらの二項係数をまとめると \(q-p\) ごとに \(O(1)\) で目標の値が計算できる．

\(h<0\) も全く同様．

よって，すべてが \(O(N+M)\) 時間で計算できる．

実装例