big 题解【异或】【字典树】【构造】

点击量：189

    最重要的部分是理解题目中给的式子。

目录

题目描述

你需要在\([0,2^n)\)中选一个整数\(x\)，接着把\(x\)依次异或\(m\)个整数\(a_1\sim a_m\)。

在你选出\(x\)后，你的对手需要选择恰好一个时刻（刚选完数时、异或一些数后或是最后），将\(x\)变为\((\lfloor\frac {2x}{2^n}\rfloor+2x)\pmod {2^n}\)。

你想使\(x\)最后尽量大，而你的对手会使\(x\)最后尽量小。

你需要求出\(x\)最后的最大值，以及得到最大值的初值数量。

输入输出格式

输入格式：

第一行两个整数\(n,m\)。第二行\(m\)个整数\(a_1\sim a_m\)。

输出格式：

第一行输出一个整数，表示\(x\)最后的最大值。

第二行输出一个整数，表示得到最大值的初值数量。

第一个数正确得\(6\)分，两个数都正确再得\(4\)分。

输入输出样例

输入样例#1：

2 3
1 2 3

输出样例#1：

1
2

说明

样例解释：

\(x=0\)时得到\(0\)，\(x=1\)时得到\(1\)，\(x=2\)时得到\(1\)，\(x=3\)时得到\(0\)。

数据范围：

对于\(20\%\)的数据，\(n\le 10,m\le 100\)。

对于\(40\%\)的数据，\(n\le 10, m\le 1000\)。

对于另外\(20\%\)的数据，\(n\le 30,m\le 10\)。

对于\(100\%\)的数据\(n\le 30,m\le 100000,\ 0\le a_i<2^n\)。

题解：

    这个题看上去比较难，而且式子很麻烦。实际上这个式子是在将\(x\)左移一位，如果原来最高位是\(1\)，那么移动后的最低位补为\(1\)。

    这样这个题的过程就是，你给出一个数\(x\)，你的对手在这个数异或\(\bigoplus\limits_{i=1}^{k}a_i\)的异或和后，将所得结果左移一位得到\(x’\)，接着将\(x’\)异或\(\bigoplus\limits_{i=k+1}^{m}a_i\)。而可以发现，前面两个操作可以等价于\(x\)先左移一位再依次异或\(a_i\times 2\ (1\le i\le k)\)（左移一位），\(k+1\)以后的就直接异或原数。这样我们有\(m+1\)个\(k\)，而异或是有结合律的，因此可以把每种状态后面所有的\(a_i\)都看作是一个数\(b_i\)。比如当\(k=3\)时，\(b_i=2a_1\bigoplus 2a_2\bigoplus 2a_3\bigoplus a_4\bigoplus \dots \bigoplus a_m\)。

    此时题目转化为，求\(x\)使得\(\min\limits_{i=0}^m x\bigoplus b_i\)最大。此时认为，如果对于任意\(i\in[0,m]\)，都有\(b_i\)的第\(k\)位相等，那么就一定可以构造出\(x\)使它与任意\(b_i\)异或在这一位上都为\(1\)，即当\(b_i\)的第\(k\)位均为\(0\)时，让\(x\)的第\(k\)位为\(1\)即可，反之亦可。如果\(b_i\)的第\(k\)位既有\(0\)又有\(1\)，说明这一位会被对手抢走。

    又因为我们要找出最大的异或答案，那么我们找出尽可能高的这种二进制位。既然我们可以利用\(a_i\)的前缀后缀和求出上面任何一个\(b_i\)，然后把它插入字典树中。然后dfs这棵字典树，如果一个节点拥有两个儿子，就对应上面说明这里无论选\(0\)还是\(1\)，对手都会让你变成\(0\)，同时dfs两个儿子，继续统计；如果只有一个儿子，“你”就可以选择另一个儿子代表的数字，为答案做出\(n-dep\)的贡献，这里的\(dep\)是字典树节点的深度。最终统计答案就和一般的计数一样就可以了。

    又是一个异或计数的好题公式误导人类啊……

Code：

#include<cstdio>
#include<cstring>
struct node
{
    node *ls,*rs;
    node()
    {
        ls=NULL;
        rs=NULL;
    }
}*root=new node();
void Insert(node *rt,int x,int d)
{
    if(d==-1)
        return;
    if((x>>d)&1)
    {
        if(!rt->rs)
            rt->rs=new node();
        Insert(rt->rs,x,d-1);
    }
    else
    {
        if(!rt->ls)
            rt->ls=new node();
        Insert(rt->ls,x,d-1);
    }
}
int a[100100];
int sum[100100],mus[100100];
int mx=0,cnt=0,now=0;
void dfs(node *rt,int d)
{
    if(d==-1)
    {
        if(now==mx)
            ++cnt;
        if(now>mx)
        {
            mx=now;
            cnt=1;
        }
        return;
    }
    if(rt->ls&&rt->rs)
    {
        dfs(rt->ls,d-1);
        dfs(rt->rs,d-1);
    }
    else
    {
        now|=(1<<d);
        rt->ls?dfs(rt->ls,d-1):dfs(rt->rs,d-1);
        now^=(1<<d);
    }

}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;++i)
        sum[i]=sum[i-1]^(((1<<n)-1)&(a[i]<<1)|(a[i]>>(n-1)));//前缀异或和 表示前面都左移
    for(int i=m;i>=0;--i)
        mus[i]=mus[i+1]^a[i+1];//直接后缀异或和
    for(int i=0;i<=m;++i)
        Insert(root,sum[i]^mus[i],n-1);
    dfs(root,n-1);
    printf("%d\n%d\n",mx,cnt);
    return 0;
}