ABC168-E ・(Bullet) - zawatinはてなブログ

考察を楽しめました。

問題概要
- 制約
考察
- の時
- の時
- 解法
提出コード

問題概要

https://atcoder.jp/contests/abc168/tasks/abc168_e

$N$ 要素の整数の２つ組の列 $( (A_{1}, B_{1})\, (A_{2}, B_{2})\, \dots\, (A_{N}\, B_{N}) )$ を与えます*1。列から一つ以上の要素を選び出す方法で、どの選んだ2要素 $(A_{i}, B_{i}),\ (A_{j}\, B_{j})$ についても $A_{i}\cdot A_{j} + B_{i}\cdot B_{j}\ne 0$ を満たすようなものの通り数を $10^{9} + 7$ で割ったあまりを出力してください。

制約

$1\le N\le 2\times 10^{5}$
$\mid A_{i}\mid \, \mid B_{i}\mid\le 10^{18}$

考察

$(A_{i}, B_{i})$ を $\mathbb{R}^{2}$ のベクトル $\vec{v}_{i}$ (言い方合ってますかね？)とみなすと。条件 $A_{i}\cdot A_{j} + B_{i}\cdot B_{j}\ne 0$ は内積 $\vec{v}_{i}\cdot \vec{v}_{j}$ が $0$ でないと言い換えることができます。

$\vec{v}_{i}\cdot \vec{v}_{j} = \mid \vec{v}_{i}\mid \mid \vec{v}_{j}\mid \cos \theta \ne 0$ なので $\mid \vec{v}_{i}\mid = 0$ の時と $\cos \theta = 0$ の時を場合分けして考えることにします

$\mid \vec{v}_{i}\mid = 0$ の時

$\vec{v}_{i} = (0, 0)$ の場合に限ります。このような $\vec{v}_{i}$ を選んでしまった場合、他のどのような要素に対しても内積が $0$ になってしまい条件に違反します。よってこのような $\vec{v}_{i}$ を選ぶ時は他のベクトルを同時に選んではいけないことがわかります。

$\cos \theta = 0$ の時

いわゆる「ベクトルが直交する時」ですね。すべてのペアについてベクトルが直交しているか確かめるのはTLに間に合わないので工夫して２つのベクトルが直交するか確かめなければなりません。

ここで、二次元平面上で原点と点 $(A_{i}\, B_{i})$ を通る直線を考えます。 $\vec{0}$ でないベクトル $v_{i}$ 、 $v_{j}$ が直交することは、対応する直線が直交することと同値です。よって直線毎に考えます。ベクトルが $N$ 個しか無いのと、ある(原点を通る)直線と直交する(原点を通る)直線はちょうど一本しか無いので考えるべき直線は高々 $O(N)$ 個しかありません。

ある列上２つのベクトルが同じ直線に対応する時、その２つのベクトルは同一のベクトルが２つあると考えて良いです。なぜなら

その２つのベクトルは明らかに直交していない
片方のベクトルと直交する列上のベクトルの集合と、もう片方のベクトルと直交する列上のベクトルの集合は一致する

からです。

解法

以上より、以下のような手続きで条件を満たすような選び方を数え上げることができます。

考えるべき $O(N)$ 個の直線を予め列挙しておく、直線毎に対応するベクトルの数と直交する直線を高速に取り出せるようにしておく(連想配列等でできると思います)
$\text{ans} = 1$ とする。それぞれの直線に対して探索済か否かを記憶する列を用意しておき、すべての直線に対して未探索としておく
未探索の直線を一本自由に選ぶ(Pとする)。選んだ直線と直交する直線(Qとする)を取り出す(そのような直線は必ず未探索である)
P, Qに対応するベクトルの数をp, qとしてにを掛ける
- Pに対応する方から選ぶ通り数とQに対応する方から選ぶ通り数を掛けています。
- Pに対応するベクトルとQに対応するベクトルを同時にえらぶことはできないことに注意してください
- 二回空集合を数えているので、 $-1$ しています
P, Qを探索済とする
すべての直線が探索すみになるまで、3 ~ 5を繰り返す
$(0, 0)$ の分を $\text{ans}$ に足す。最後に $\text{ans}$ から $1$ を引く(空集合の分)

提出コード

実装がうまくできなくてかなりぐちゃぐちゃなコードになってしまいました

#include <bits/stdc++.h>
#include <atcoder/modint>
using i32 = int;
using i64 = long long;
using Point = std::pair<i64, i64>;
using mint = atcoder::modint1000000007;
using namespace std;

void minify(i64& x, i64& y) {
    i64 g = gcd(x, y);
    if (g == 0) return;
    x /= g;
    y /= g;
    if (x < 0) {
        x *= -1;
        y *= -1;
    }
    if (x == 0 and y < 0) { // これ忘れててペナを連発してしまった
        y *= -1;
    }
}

void main_() {
    i32 N; cin >> N;
    map<Point, i32> buc;
    for (i32 _ = 0 ; _ < N ; _++) {
        i64 x, y; cin >> x >> y;
        minify(x, y);
        buc[{ x, y }]++;
    }
    map<Point, i32> idx;
    i32 sz = 0;
    for (const auto& [p, _] : buc) idx[p] = sz++;
    vector<Point> P;
    for (const auto& [p, _] : buc) P.push_back(p);
    // assert(P.size() == (size_t)sz);
     
    vector<i32> orh(sz, -1); 
    for (i32 i = 0 ; i < sz ; i++) {
        auto [x, y] = P[i];
        i64 rx = -y, ry = x;
        minify(rx, ry);
        if (idx.count({ rx, ry })) {
            orh[i] = idx[{ rx, ry }];
        }
    }

    const i32 mN = 200010;
    vector<mint> pow2(mN, mint{1});
    for (i32 i = 0 ; i + 1 < mN ; i++) {
        pow2[i + 1] = pow2[i] * 2;
    }

    mint ans{1};
    vector<bool> used(sz, false);
    set<i32> st;
    for (i32 i = 0 ; i < sz ; i++) {
        if (used[i]) continue;
        if (P[i] == Point{ 0LL, 0LL }) continue;
        if (orh[i] == -1) {
            ans *= pow2[buc[P[i]]];
            used[i] = true;
        }
        else {
            assert(i < orh[i]);
            // assert(orh[i] != i);
            // assert(used[orh[i]] == false);
            ans *= pow2[buc[P[i]]] + pow2[buc[P[orh[i]]]] - 1;
            used[i] = used[orh[i]] = true;
        }
    }

    ans += buc[{ 0LL, 0LL }];
    ans -= 1;

    // assert(count(used.begin(), used.end(), true) == (i32)used.size());

    cout << ans.val() << endl;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    main_();
    return 0;
}

*1:外側の括弧と内側の括弧の間にスペースを入れることで脚注と認識させないテク。はてなブログ典型90ですか？