C++の練習を兼ねて, AtCoder Regular Contest 064 の 問題F (Rotated Palindromes) を解いてみた.
■感想.
1. 問題F は, 解答方針が, 全く見えなかったので, 解答を参照の上, 実装して何とかAC版となった.
2. 整数を, 2で割ったときの 切り下げ と 切り上げ を誤認してしまい, 誤りの訂正に時間かかってしまった(汗).
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトARC 064 解説をご覧下さい.
■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 96 |
// C++(GCC 9.2.1) // 解き直し. // https://img.atcoder.jp/arc064/editorial.pdf // ① 1_27.txt, 1_28.txt, 1_30.txt, 1_31.txt で, WA版となったため, ロジック修正. // -> d[i] / 2 は d[i] * 500000004 % MOD に 修正 -> 最終的に, もとに戻した. // ② 1_27.txt で, WA版となったため, ロジック修正. // -> mPow の 第二引数が, 切り捨てだったものを, 切り上げに修正. // ③ 2. 例外. を 廃止. // -> ② の 修正でカバーできるため. #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--) #define pb push_back #define all(x) x.begin(), x.end() const LL MOD = 1e9 + 7; // 与えられた正の整数のすべての約数を抽出. // @param X: 約数を抽出したい正の整数. // @return ret: すべての約数. vector<LL> div(LL X){ vector<LL> ret; ret.pb(1); for(LL d = 2; d * d <= X; d++){ if(X % d == 0){ ret.pb(d); if(d * d != X) ret.pb(X / d); } } if(X > 1) ret.pb(X); sort(all(ret)); return ret; } // 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; } int main(){ // 1. 入力情報. LL N, K; scanf("%lld %lld", &N, &K); // 2. 例外. // if(N == 1){ // printf("%lld\n", K); // return 0; // } // 3. N の 約数. vector<LL> d = div(N); // for(auto &p : d) printf("%lld ", p); // puts(""); // 4. 各最小周期に対応する数列の個数. int l = d.size(); LL num[l]; memset(num, 0, sizeof(num)); rep(i, l){ // num[i] = mPow(K, d[i] / 2); // num[i] = mPow(K, d[i] * 500000004 % MOD); num[i] = mPow(K, (d[i] + 1) / 2); rep(j, i){ if(d[i] % d[j] == 0) num[i] = (num[i] + MOD - num[j]) % MOD; } } // 5. 解答を求めるための数式を計算. LL ans = 0, nd; rep(i, l){ // nd = (d[i] & 1) ? d[i] : d[i] / 2; // nd = (d[i] & 1) ? d[i] : (d[i] * 500000004 % MOD); nd = (d[i] & 1) ? d[i] : d[i] / 2; ans += num[i] * nd; ans %= MOD; } // 6. 出力. 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 |
[入力例] 4 2 [出力例] 6 ※AtCoderテストケースより [入力例] 1 10 [出力例] 10 ※AtCoderテストケースより [入力例] 6 3 [出力例] 75 ※AtCoderテストケースより [入力例] 1000000000 1000000000 [出力例] 875699961 ※AtCoderテストケースより [入力例] 987654321 123456789 [出力例] 592610732 [入力例] 314159265 358979323 [出力例] 261668354 |
■参照サイト
AtCoder Regular Contest 064