ABC168-E ・(Bullet)

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("1 2");
            WillReturn.Add("-1 1");
            WillReturn.Add("2 -1");
            //5
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10");
            WillReturn.Add("3 2");
            WillReturn.Add("3 2");
            WillReturn.Add("-1 1");
            WillReturn.Add("2 -1");
            WillReturn.Add("-3 -9");
            WillReturn.Add("-8 12");
            WillReturn.Add("7 7");
            WillReturn.Add("8 1");
            WillReturn.Add("8 2");
            WillReturn.Add("8 4");
            //479
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct VectorInfoDef
    {
        internal long X;
        internal long Y;
    }
    static List<VectorInfoDef> mVectorList = new List<VectorInfoDef>();

    const long Hou = 1000000007;

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            VectorInfoDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            mVectorList.Add(WillAdd);
        }

        long Result = Solve();
        Console.WriteLine(Result);
    }

    class CntInfoDef
    {
        internal long Syougen1Cnt;
        internal long Syougen2Cnt;
    }

    // 傾きでベクトルをグループ化する
    static Dictionary<string, CntInfoDef> mCntInfoDict = new Dictionary<string, CntInfoDef>();

    static long Solve()
    {
        long ZeroVectorCnt = 0; // 0ベクトルの個数

        foreach (VectorInfoDef EachVector in mVectorList) {
            long CurrX = EachVector.X;
            long CurrY = EachVector.Y;

            if (CurrX == 0 && CurrY == 0) {
                ZeroVectorCnt++;
                continue;
            }

            if (CurrX == 0 && CurrY != 0) {
                CurrY /= CurrY;
            }
            if (CurrX != 0 && CurrY == 0) {
                CurrX /= CurrX;
            }

            // 原点と対称移動するか
            bool WillRotate = false;

            // Y座標がマイナスなら、原点と対称移動
            if (CurrY < 0) {
                WillRotate = true;
            }

            // Y座標が0でXが負なら、原点と対称移動
            if (CurrY == 0 && CurrX < 0) {
                WillRotate = true;
            }

            if (WillRotate) {
                CurrX *= -1;
                CurrY *= -1;
            }

            if (CurrX != 0 && CurrY != 0) {
                long GCD = DeriveGCD(Math.Abs(CurrX), Math.Abs(CurrY));
                CurrX /= GCD;
                CurrY /= GCD;
            }

            // 傾きを求める
            long XZouka = CurrX;
            long YZouka = CurrY;

            // X座標が0以下なら、-90度回転
            int CurrSyougen = 1;
            if (CurrX <= 0) {
                CurrSyougen = 2;
                long SavedXZouka = XZouka;
                long SavedYZouka = YZouka;
                XZouka = SavedYZouka;
                YZouka = -SavedXZouka;
            }

            string KeyStr = string.Format("{0},{1}", XZouka, YZouka);
            if (mCntInfoDict.ContainsKey(KeyStr) == false) {
                mCntInfoDict[KeyStr] = new CntInfoDef();
            }

            if (CurrSyougen == 1) {
                mCntInfoDict[KeyStr].Syougen1Cnt++;
            }
            if (CurrSyougen == 2) {
                mCntInfoDict[KeyStr].Syougen2Cnt++;
            }
        }

        long Answer = 1;
        foreach (var EachPair in mCntInfoDict) {
            long CurrPatternCnt = 0;

            // 第1象限から選ぶ場合の数
            CurrPatternCnt += DeriveBekijyou(2, EachPair.Value.Syougen1Cnt, Hou) - 1;
            CurrPatternCnt %= Hou;

            // 第2象限から選ぶ場合の数
            CurrPatternCnt += DeriveBekijyou(2, EachPair.Value.Syougen2Cnt, Hou) - 1;
            CurrPatternCnt %= Hou;

            // どれも選ばない場合の数
            CurrPatternCnt++;
            CurrPatternCnt %= Hou;

            Answer *= CurrPatternCnt;
            Answer %= Hou;
        }

        // 0ベクトルから選ぶ場合
        Answer += ZeroVectorCnt;

        // 1つも選ばない場合を引く
        Answer--;
        if (Answer < 0) Answer += Hou;

        return Answer;
    }

    // ユークリッドの互除法で2数の最大公約数を求める
    static long DeriveGCD(long pVal1, long pVal2)
    {
        long WarareruKazu = pVal2;
        long WaruKazu = pVal1;

        while (true) {
            long Amari = WarareruKazu % WaruKazu;
            if (Amari == 0) return WaruKazu;
            WarareruKazu = WaruKazu;
            WaruKazu = Amari;
        }
    }

    // 繰り返し2乗法で、(NのP乗) Mod Mを求める
    static long DeriveBekijyou(long pN, long pP, long pM)
    {
        long CurrJyousuu = pN % pM;
        long CurrShisuu = 1;
        long WillReturn = 1;

        while (true) {
            // 対象ビットが立っている場合
            if ((pP & CurrShisuu) > 0) {
                WillReturn = (WillReturn * CurrJyousuu) % pM;
            }

            CurrShisuu *= 2;
            if (CurrShisuu > pP) return WillReturn;
            CurrJyousuu = (CurrJyousuu * CurrJyousuu) % pM;
        }
    }
}

解説

ベクトルの内積で考えた時に、
なす角が90度なら、同時に選択できないので

まず、第3象限か第4象限が終点のベクトルは、
原点と対称移動させてます。

次に、クラスで
第1象限のベクトルの個数と、
-90度回転させた第2象限のベクトルの個数を、まとめて管理してます。

後は、場合の数の積の法則を使えばいいのですが、
零ベクトルに関しては、別途対応してます。