C++の練習を兼ねて, 競プロ典型 90 問 の 問題015 (Don’t be too close) を解いてみた.
■感想.
1. 問題015は, 解答の方針が見えなかったので, (問題015 (Don’t be too close) 解説) を参考に実装したところ, AC版に到達出来た.
2. 組み合わせ計算について, 新たな性質に触れることが出来たので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題015 を ご覧下さい.
■C++版プログラム(問題015／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 |
// 解き直し. // https://github.com/E869120/kyopro_educational_90/blob/main/editorial/015.jpg // 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; const int LIMIT = 101010; LL FAC[LIMIT], INV[LIMIT]; // 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 % 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 0LL; if(n == k || k == 0LL) return 1LL; LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD; return ret; } int main(){ // 1. 入力情報. int N; scanf("%d", &N); FAC[0] = 1; repx(i, 1, LIMIT) FAC[i] = (LL)i * FAC[i - 1] % MOD; rep(i, LIMIT) INV[i] = mPow(FAC[i], MOD - 2); // 2. クエリ回答(解説通り). // -> 差が, k以上となるように, a個のボールを選択. repx(k, 1, N + 1){ // 2-1. 選び方の総数. LL ans = 0; int u = N / k; if(N % k != 0) u++; repx(a, 1, u + 1){ LL n = (LL)(N - (k - 1) * (a - 1)); LL r = (LL)a; ans += combination(n, r); ans %= MOD; } // 2-2. 出力. 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 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 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 |
[入力例] 1 [出力例] 1 ※AtCoderテストケースより [入力例] 2 [出力例] 3 2 ※AtCoderテストケースより [入力例] 3 [出力例] 7 4 3 ※AtCoderテストケースより [入力例] 4 [出力例] 15 7 5 4 ※AtCoderテストケースより [入力例] 7 [出力例] 127 33 18 13 10 8 7 ※AtCoderテストケースより [入力例] 20 [出力例] 1048575 17710 2744 906 430 250 167 118 90 75 65 56 48 41 35 30 26 23 21 20 ※AtCoderテストケースより [入力例] 50 [出力例] 898961330 951279874 262271567 14341526 1985602 466851 153365 63191 30623 16687 9987 6453 4354 3070 2290 1790 1427 1138 910 735 605 512 448 405 375 350 326 303 281 260 240 221 203 186 170 155 141 128 116 105 95 86 78 71 65 60 56 53 51 50 ※AtCoderテストケースより [入力例] 5 [出力例] 31 12 8 6 5 [入力例] 10 [出力例] 1023 143 59 35 25 20 16 13 11 10 |
■参照サイト
015 – Don’t be too close
問題015 (Don’t be too close) 解説