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にマイナスを押し付けるとこんなに楽になるんだなぁ。勉強になりました。