ABC024 D - 動的計画法

解説

ここからはmodを取っていることを一旦忘れる。

$ A =\ _{r + c}\mathrm{C}_{r} = \frac{(r + c)(r + c - 1) \cdots (c + 1)}{r(r - 1)(r - 2) \cdots 1}

$ B =\ _{r + c + 1}\mathrm{C}_{r} = \frac{(r + c + 1)(r + c) \cdots (c + 2)}{r(r - 1)(r - 2) \cdots 1}

$ C =\ _{r + c + 1}\mathrm{C}_{r + 1} = \frac{(r + c + 1)(r + c) \cdots (c + 1)}{(r + 1)r(r - 1) \cdots 1}

を利用する。

上の3つの式を見ると、同じような数を掛けているのが分かる。そこで、それぞれの比を取ってみると

$ \frac{B}{A} = \frac{r + c + 1}{c + 1}\ \cdots \ ①

$ \frac{C}{A} = \frac{r + c + 1}{r + 1}\ \cdots \ ②

大分いい感じの式が出てきたので、①と②をそれぞれ整理すると、

$ Ar + (A - B)c + (A - B) = 0

$ (A - C)r + Ac + (A - C) = 0

$ r = \frac{BC - AC}{AB + AC - BC},\ c = \frac{BC - AB}{AB + AC - BC}

という解が出てくる。後はこれをmodの逆元を使って求めるとACできる。

補足

ここ分かりません　多分式変形したら正しいと思うけど…

感想

連立一次方程式が見えたので楽しかった