ABC168 E - ∙ (Bullet)
問題原文
解法
実験とかすると、 は としていいことは分かる。(一旦0は無視で)
これをとりあえず集計したくなる。
集計の結果、例えば が 個、 と仲が悪いものの個数が 個 ということがわかれば、
S からも Tからも選ばない
S から1つ以上選ぶ
T から 1つ以上選ぶ
通り数を足し合わせたものがそのキーに関しての通り数となって、答えが計算できそうということがわかる。
ただ、 と仲が悪いものは、 であったり、 であったりしてめんどくさい。
これは、片方がマイナスのものはマイナスを の方に押し付けることで、まとめて集計できる。
(たとえば、 は として集計する)
また、 のようなものは のようにしても問題ないので、そのようにして集計する。
のような片方0に関しては、 仲が悪いものは のようなもう片方が0のものになる。
後々計算しやすくするように、 が 0なら として、 が 0 なら として集計しておく。
は他の全てと仲が悪いので、「 から1つ選ぶ」という組合せを完全に別で計算する必要がある。
これは普通に の数を数えておくことでできる。
実装
複雑ではないんだけどひ〜
from math import gcd from collections import defaultdict N = int(input()) MOD = 10 ** 9 + 7 zero_zero_num = 0 fishes = defaultdict(int) for i in range(N): a, b = map(int, input().split()) if a == 0 and b == 0: zero_zero_num += 1 elif a == 0: fishes[(0, -1)] += 1 elif b == 0: fishes[(1, 0)] += 1 else: g = gcd(a, b) a, b = a // g, b // g if (a > 0 and b > 0) or (a < 0 and b < 0): fishes[(abs(a), abs(b))] += 1 else: a, b = (-a, -b) if a < 0 else (a, b) fishes[(a, b)] += 1 ans = 1 keys = list(fishes.keys()) visited = set() for (kai, kbi) in keys: if kbi >= 0: kaj, kbj = kbi, -kai else: kaj, kbj = -kbi, kai if ((kai, kbi) in visited) or ((kaj, kbj) in visited): continue ans *= (1 + (pow(2, fishes[(kai, kbi)], MOD) - 1) + (pow(2, fishes[(kaj, kbj)], MOD) - 1)) ans %= MOD visited.add((kai, kbi)) visited.add((kaj, kbj)) print((ans + zero_zero_num - 1) % MOD)
感想
キーを集計しやすいようにあらかじめ変形する
みたいなテク?なのかな。。。
bにマイナスを押し付けるとこんなに楽になるんだなぁ。勉強になりました。