\(f(A)\) をより見通しのよい方法で解釈します．

天下り的ですが，次のような問題を考えます．

• 座標 \(0\) から出発し，座標を \(+1\) or \(-1\) する操作を \(N+2M\) 回繰り返し，座標 \(N\) へと向かう．座標は常に \([0,N]\) の範囲に収まるようにする． ここで，座標 \(i \to (i-1)\) という操作が \(A_i\) 回行われたとする． このような移動は何通りあるか？

各 \(i=1,2,\cdots,N-1\) について，座標 \(i\) に到着したあとに右/左のどちらに移動するかを考えるだけでこの問題は解けます． 結局，各 \(i\) について \({A_i+A_{i+1} \choose A_i}\) 通りの選択肢があるため，この問題の答えは \(f(A)\) になります．

もとの問題には \(A_1=K\) という制約がついていました． これを踏まえると，問題は次のように言いかえられます．

• 座標 \(0\) から出発し，座標を \(+1\) or \(-1\) する操作を \(N+2M\) 回繰り返し，座標 \(N\) へと向かう．座標は常に \([0,N]\) の範囲に収まるようにする． 座標 \(0\) に戻ってくる回数 (初期状態は含まない) がちょうど \(K\) 回であるような移動方法は何通りあるか？

\(i\) 回の移動によって初めて座標 \(0\) に戻ってくる移動方法の数を \(f_i\) とおきます． また，\(i\) 回の移動によって，座標 \(0\) に戻ってくることなく座標 \(N\) へ向かう移動方法の数を \(g_i\) と置きます． \(f_i,g_i\) が求まれば，あとは多項式のべき乗と畳込みで答えがでます．

\(f_i,g_i\) の求め方について考えます． まず，素朴な DP により \(O(N(N+M))\) 時間で計算することができます． このままだと \(N\) が大きい場合に困るので別の計算方法も必要です．

問題を \(2\) 次元グリッド上の移動で定式化してみます． すると，\(2\) つの斜め直線に囲われた領域を進む問題になります． これはカタラン数の数え上げと同じ要領で，鏡像法によって計算できます． 計算量は \(O((N+M)^2/N)\) になります． （具体的な計算方法については実装例を参考にしてください．）

以上の \(2\) つの方法のうち計算量の小さい方を採用することで，\(O((N+M)^{1.5})\) 時間で \(f_i,g_i\) が計算できます．

多項式のべき乗は \(O((N+M) \log (N+M))\) で計算できるため．計算量は全体で \(O((N+M)^{1.5})\) になります．

実装例

おまけ \(O((N+M) \log{(N+M)})\)解法