Grid partitioning

$f(N,M,K)$を求める値とします。

• 右に移動すると$N$マス確定するので$f(N,M-1,K-N)$
• 上に移動すると確定マスはないので$f(N-1,M,K)$

これを元にDPを行えばよいです。

$f(N,M,K)=f(N,M-1,K-N)+f(N,M-1,K-N)$

---

余談(本題)

この問題の答えは「$K$を$N$個以下の『$M$以下の非負整数』に分割する方法の数」と一致します。ヤング図形みたいな感じで考えたら分かると思います。

実はこの問題、DPだと$O(NMK)$かかりますが、形式的冪級数を用いると$O(K\log{K})$で解くことができます■。すごいですね。

$O(K\log{K})$アルゴリズムを置いておきたかったという理由だけでこの問題作りました。

ちなみに、問題から分かることですが、

• $K\leftarrow NM-K$
• $N\leftarrow \min(N,K)$
• $M\leftarrow \min(M,K)$
• $swap(N,M)$

とかの操作をしても答えは変わりません。