C++の練習を兼ねて, AtCoder Regular Contest 046 の 問題D (うさぎとマス目) を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考にして, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 046 解説 を ご覧下さい.
■C++版プログラム(問題D/AC版).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
// 解き直し. // https://www.slideshare.net/chokudai/arc046 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) const LL MOD = 1e9 + 7; LL FAC[2020202], INV[2020202]; // Fermat's little theorem から, 大きな冪乗の計算を行う. // @param a: べき乗したい正整数. // @param b: 指数. // @return: べき乗した計算結果(mod版). LL mPow(LL a, LL b){ LL t = 1; while(b){ if(b & 1) t = (t * a) % MOD; a = a * a % MOD; b >>= 1; } return t; } // 組み合わせ(nCk)計算用(mod版). // ※配列FAC, INV は, 事前に計算済のものを使う. // @param n: 対象となる要素の個数. // @param k: 選択する要素の個数. // @return: 組み合わせ(nCk)の計算結果(mod版). LL combination(LL n, LL k){ if(n < 0 || k < 0 || k > n) return 0LL; if(n == k || k == 0LL) return 1LL; LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD; return ret; } int main(){ // 1. 入力情報. LL H, W; scanf("%lld %lld", &H, &W); // 2. 事前計算. FAC[0] = INV[0] = 1; rep(i, 2020202){ FAC[i + 1] = (LL)(i + 1) * FAC[i] % MOD; INV[i + 1] = mPow(FAC[i + 1], MOD - 2); } // 3. 全探索(解説通り). LL ans = 0, d = __gcd(H, W); repx(x, 1, (int)d){ LL w = W / __gcd(W, (LL)x); LL h = H / __gcd(H, (LL)(d - x)); LL g = __gcd(w, h); if(w / g * h == H / d * W) ans = (ans + combination(d, x)) % MOD; } // 4. 出力. printf("%lld\n", ans); return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
[入力例] 2 2 [出力例] 2 ※AtCoderのテストケースより [入力例] 6 3 [出力例] 3 ※AtCoderのテストケースより [入力例] 3 4 [出力例] 0 ※AtCoderのテストケースより [入力例] 10 10 [出力例] 260 ※AtCoderのテストケースより [入力例] 200 300 [出力例] 551887980 ※AtCoderのテストケースより [入力例] 7 7 [出力例] 126 [入力例] 77 121 [出力例] 1716 [入力例] 120 108 [出力例] 816 [入力例] 2022 828 [出力例] 12 [入力例] 72 96 [出力例] 5769552 |
■参照サイト
AtCoder Regular Contest 046