C++の練習を兼ねて, AtCoder Beginner Contest 168 の 問題E (∙ (Bullet)) を解いてみた.
■感想.
1. 実装に苦労したものの, 何とかAC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 168 解説をご覧下さい.
■C++版プログラム(問題E/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 97 98 99 100 101 102 103 104 105 106 107 108 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<LL, LL>; #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 a first #define b second const LL MOD = 1e9 + 7; LL mPow2[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); map<P, LL> m; LL a, b, g, ga, gb; int z = 0; rep(i, N){ scanf("%lld %lld", &a, &b); // 両方ゼロの場合を保存. if(a == 0 && b == 0){ z++; continue; } // 片方ゼロの場合を保存. if(a == 0 && b != 0){ m[{0, 1}]++; continue; } // 片方ゼロの場合を保存. if(a != 0 && b == 0){ m[{1, 0}]++; continue; } // 最大公約数. ga = abs(a); gb = abs(b); g = __gcd(ga, gb); a /= g; b /= g; // 符号調整. if(a < 0 && b < 0) a = -a, b = -b; if(a > 0 && b < 0) a = -a, b = -b; // 保存. m[{a, b}]++; } // 2. 2 の べき乗 を 保存. mPow2[0] = 1; rep(i, 202019) mPow2[i + 1] = (mPow2[i] << 1), mPow2[i + 1] %= MOD; // 3. 仲が悪い組み合わせを調査. set<P> used; // すでに確認したペアであるか判定. vector<P> bad; // 仲の悪い組み合わせの個数のペアを保存. LL res = (LL)(N - z); // 残数. for(auto &p : m){ LL sd = p.a.a, sf = p.a.b, sc = p.b; LL od = sf, of = sd; if(of < 0) of = -of; else od = -od; P op = {od, of}; if(used.count(p.a) == 0){ used.insert(p.a); if(m.count(op) > 0){ used.insert(op); bad.pb({sc, m[op]}); // 残数更新. res -= sc; res -= m[op]; } } } // 4. イワシの選び方は? LL ans = 1; rep(i, (int)res) ans <<= 1, ans %= MOD; for(auto &p : bad){ int pa = (int)p.a, pb = (int)p.b; LL t = ((mPow2[pa] + mPow2[pb]) % MOD + MOD - 1) % MOD; ans *= t; ans %= MOD; } // 5. ゼロの場合を考慮. ans += (LL)z; ans %= MOD; // 6. 全く選択しないパターンを考慮. ans += (MOD - 1); ans %= MOD; // 7. 出力. 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 |
[入力例] 3 1 2 -1 1 2 -1 [出力例] 5 ※AtCoderテストケースより [入力例] 10 3 2 3 2 -1 1 2 -1 -3 -9 -8 12 7 7 8 1 8 2 8 4 [出力例] 479 ※AtCoderテストケースより [入力例] 51 3 1 -4 1 5 -9 2 6 -5 3 5 8 9 -7 9 3 2 -3 8 4 -6 2 6 4 3 -3 8 3 -2 7 9 5 0 -2 8 -8 4 1 9 -7 -1 6 9 3 9 9 3 7 -5 10 5 -8 2 0 9 -7 4 -9 4 4 5 9 2 -3 0 7 8 -1 6 4 0 6 2 8 6 -2 0 8 9 9 -8 6 2 8 0 3 4 8 2 5 -3 4 -2 1 1 7 0 6 7 9 8 2 [出力例] 173136412 |
■参照サイト
AtCoder Beginner Contest 168