AtCoder Beginner Contest 145 D - 今日から始める競プロ日記
はじめに
AtCoder Beginner Contest 145 に参加しました。
D問題の二項係数の計算で躓いてしまったので、 この記事にまとめておきます。
D - Knight
- 二元グリッド上の (0, 0) にナイトの駒がいる
- ナイトは (i+1, j+2) か (i+2, j+1) に動かせる
- このナイトを (X, Y) に移動させる方法は何通りか
解いた方針
以下を参考に解き方をまとめます。
(+1, +2)を行う回数をn、(+2, +1)を行う回数をmとすると以下の連立方程式が立てられます。
2n + m = X n + 2m = Y
これを解くとnとmを求めることができます。
n = (2Y-X) / 3 m = (2X-Y) / 3
そして、n+m回の移動のうち、(+1, +2)と(+2, +1)の組み合わせは、n+m C nで求められます。
また、この計算ではmodをとる必要があります。
以下のけんちょんさんの記事を参考にしました。
よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方 - けんちょんの競プロ精進記録
コード
二項係数の計算はけんちょんさんのコードをそのまま使っているので、 もしその部分を使う場合はけんちょんさんの記事を参考にしてください。
int main()
{
long long X, Y;
scanf("%lld%lld",&X,&Y);
if((X+Y)%3!=0){printf("0\n");return 0;}
long long n=(2*Y-X)/3;
long long m=(2*X-Y)/3;
if(n<0||m<0){printf("0\n");return 0;}
long long nm=n+m;
COMinit();
cout << COM(nm,n) << endl;
return 0;
}
おわりに
modのとり方がいまだによく分かりません......。
