C++の練習を兼ねて, AtCoder Beginner Contest 154 の 問題F (F – Many Many Paths) を解いてみた.
■感想.
1. 高速に計算する方法が見えなかったので, 解説を確認して実装した.
2. 組み合わせの性質を, 新しく仕入れることが出来たので, 個人的には, 大満足だった.
3. 引き続き, たくさんの過去問を振り返っていきたいと思う.
本家のサイトABC 154解説をご覧下さい.
■C++版プログラム(問題F/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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
// 解き直し. // https://img.atcoder.jp/abc154/editorial.pdf #include <bits/stdc++.h> using namespace std; using LL = long long; #define repex(i, a, b, c) for(LL i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) const LL MOD = 1e9 + 7; const int LIMIT = 2020202; LL FAC[LIMIT]; LL INV[LIMIT]; // Fermat's little theorem から, 大きな冪乗の計算を行う. // @param a: べき乗したい正整数. // @param b: 指数. // @return: べき乗した計算結果(mod版). LL inverse(LL a, LL b){ LL t = 1; while(b){ if(b & 1) t = (t * a) % MOD; a = a * a % MOD; b >>= 1; } return t % MOD; } // 組み合わせ(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 0; LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD; return ret; } // (0, 0) ~ (r, c) の範囲で, 組み合わせ(nCk) の 総和 を 計算. // @param r: (目的地の)行番号. // @param c: (目的地の)列番号. // @return : 計算結果(mod版). LL S(LL r, LL c){ // TLE版. // ex. // 12345 123 54321 543 // -> 614939681 の 出力で, 481[ms] かかった. // LL ret = 0; // rep(i, r + 1) rep(j, c + 1) ret += combination(i + j, i), ret %= MOD; // 高速版(解説通り). LL ret = combination(r + 1 + c + 1, c + 1); ret += MOD; ret--; ret %= MOD; return ret; } int main(){ // 1. 入力情報. LL r1, c1, r2, c2; scanf("%lld %lld %lld %lld", &r1, &c1, &r2, &c2); FAC[0] = 1; repx(i, 1, LIMIT) FAC[i] = i * FAC[i - 1] % MOD; rep(i, LIMIT) INV[i] = inverse(FAC[i], MOD - 2) % MOD; // 2. チェック. assert(S(0, 0) == combination(1 + 1, 1) - 1); assert(S(0, 1) == combination(1 + 2, 2) - 1); assert(S(1, 0) == combination(2 + 1, 1) - 1); assert(S(1, 1) == combination(2 + 2, 2) - 1); assert(S(5, 8) == combination(6 + 9, 9) - 1); assert(S(12, 15) == combination(13 + 16, 16) - 1); // 3. 経路数の総和を計算(解説通り). // S(r, c) = ΣΣf(i, j) (0 <= i <= r, 0 <= j <= c) と置くと, // S(r2, c2) - S(r2, c1 - 1) - S(r1 - 1, c2) + S(r1 - 1, c1 - 1) で 計算可能とのこと. // また, S(r, c) = f(r + 1, c + 1) - 1 となることを使うらしい. LL ans = 0; ans += S(r2, c2); ans += MOD; ans -= S(r2, c1 - 1); ans %= MOD; ans += MOD; ans -= S(r1 - 1, c2); ans %= MOD; ans += S(r1 - 1, c1 - 1); ans %= 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 |
[入力例] 1 1 2 2 [出力例] 14 ※AtCoderテストケースより [入力例] 314 159 2653 589 [出力例] 602215194 ※AtCoderテストケースより [入力例] 2 3 5 7 [出力例] 2884 [入力例] 577 2156 64901 532860 [出力例] 939635786 [入力例] 120 2056 90315 959428 [出力例] 689057583 [入力例] 111111 222222 333333 444444 [出力例] 548411328 [入力例] 1 1 1000000 1000000 [出力例] 625314154 |
■参照サイト
AtCoder Beginner Contest 154