LibreOJ #114. k 大异或和

二次联通门 : LibreOJ #114. k 大异或和

/*

    LibreOJ #114. k 大异或和

    WA了很多遍

    为什么呢。。。

    一开始读入原数的时候写的是for(;N--;)

    而重新构造线性基的时候要用到N。。。所以GG

    对于找第k大异或和

    只需把原来的线性基重新构造

    构造规则为

        若i<j， aj的第j位是1，就把aj异或上ai

    查询的时候将k二进制拆分，对于1的位，就异或上对应的线性基。

    最终得出的答案就是k小值。

*/

#include <cstring>

#include <cstdio>

inline void read (long long &now)

{

    register char word = getchar ();

    bool temp = false;

    for (now = ; word < '' || word > ''; word = getchar ())

        if (word == '-')

            temp = true;

    for (; word >= '' && word <= ''; now = now *  + word - '', word = getchar ());

    if (temp)

        now = -now;

}

long long N, M;

class Linear_Base_Type

{

    static const int _L = ;

    private :

        long long number[_L + ];

        long long data[_L + ];

        int Count;

    public :

        Linear_Base_Type ()

        {

            memset (data, , sizeof data);

            memset (number, , sizeof number);

            Count = ;

        }

        inline void Insert (register long long key)

        {

            for (register int i = _L; i >= ; i --)

                if (key & (1LL << i))

                {

                    if (number[i] == )

                    {

                        number[i] = key;

                        break;

                    }

                    key ^= number[i];

                }

            return ;

        }

        void Re_Build ()

        {

            for (register int i = , j; i <= _L; i ++)

                for (j = ; j < i; j ++)

                    if ((1LL << j) & number[i])

                        number[i] ^= number[j];

            for (register int i = ; i <= _L; i ++)

                if (number[i])

                    data[Count ++] = number[i];

        }

        inline long long Query_kth (register long long k)

        {

            long long res = ;

            if (Count != N)

                -- k;

            if (k >= (1LL << Count))

                return -;

            for (register int i = ; i <= _L; i ++)

                if (k & (1LL << i))

                    res ^= data[i];

            return res;

        }

};

Linear_Base_Type Make;

int main (int argc, char *argv[])

{

    long long x;

    read (N);

    for (int i = ; i <= N; i ++)

    {

        read (x);

        Make.Insert (x);

    }

    read (M);

    for (Make.Re_Build (); M --; )

    {

        read (x);

        printf ("%lld\n", Make.Query_kth (x));

    }

    return ;

}