まよコン 2023-02-17 - mintisalive24のブログ

（+1, +2）, (+2, +1)

★マスの移動は下記のように分解できる。
(+1, +2 ) = (0, 1) + (1, 1)
(+2, +1 ) = (1, 0) + (1, 1)

n * m の格子点の左下から右上に行く問題に帰着できる。

また、一回移動するたびに　x + y = +3
移動回数をnとすると $n = \dfrac {x + y}{3}$

合計でn回移動するため、目標地点（格子の右上の点）は(X-n, Y-n) となる。
これを (A, B) とすると

${}_{A+B} C_{A}$
↑と→の矢印の並べ方

により答えが求められる。
なお、X+Yが３の倍数でない時はたどり着けない。

また、コンビネーションを求めるのに逆元を用いる。

${}_n C_{k} = \dfrac {n!} {k! (n-k)! }$

p: 素数
 フェルマーの小定理より
$x^{p-1} \equiv 1 (mod p)$
$x^{p-2} \equiv 1/x (mod p)$

よくわからん

よくわからん

★DP＋重複をどうやって避けるか