ABC024 D. 動的計画法

問題

10^8*10^8マスにmod (10^9+7)を取ったパスカルの三角形が書かれている。
今、(r,c)と(r,c+1)と(r+1,c)に書かれている数字A,B,Cがそれぞれ与えられる。
rとcのうち、10^8-1未満となるrとcで、rが最小となるもの、かつ、同じrで複数ある場合はcが最小となるものを返せ。
答えは0<=r,c<10^8-1となるものが存在するA,B,Cが与えられることが保障されている。

考え方

(r,c)に書かれている数値は(r+c)_C_c mod (10^9+7)の値になっている。
modが素数であるので+,-,*と割り算は逆元として四則演算が行え、r,cの2つの変数に対して、関係式が2つ作れるので、連立方程式を作ることができる。

関係式は、コンビネーションの計算式から、
B=(r+c+1)*A/(c+1)
C=(r+c+1)*A/(r+1)
の2つが作れ、解くと、
c=(B*C-A*B)/(A*C+A*B-B*C)
r=((B-A)-(A-B)*c)/A
となり、割り算は逆元を使うことを忘れずに計算すると、それぞれ求められる。
答えは10^8-1未満に必ず存在することが保障されているので、10^9+7でMODを取っていても問題ない。

反省

(r,c)の値はr_C_cじゃなくて(r+c)_C_c。サンプルでちゃんと確認する。