LINK：小V的序列

考试的时候 没想到正解 于是自闭.

题意很简单 就是 给出一个序列a 每次询问一个x 问序列中是否存在y 使得x^y的二进制位位1的个数<=3.

容易想到 暴力枚举。

第一个想法是在trie树上乱跳 但是可以证明 和直接暴力无异.

暴力是 mlog^3的。

可以两头枚举 枚举n的生成一次 枚举m的变化两次 利用hash存前者.

复杂度降到mlog^2. 这个做法 时间和空间两个都爆。

正解：二进制数有 64位 只要求三个位置不同 那么 我们画出这三个位置 可以发现 三个位置中一定有两个位置之间相差16位.

利用16位二进制数来分段 那么相当于 n个数都均摊给2^16.

那么每一个2^16的地方 都最多有10个数字左右。

对于询问 我们也是分段然后查询即可。

由于数据基本上算是随机 所以这样做复杂度位均摊所以是正确的。

如果存在答案 可以证明 一定可以找到答案所在.

注意 输入64位整数的格式为%llu 常数写的不要太大.

const ll MAXN=1000010,INV=(mod+1)/2;

ll n,m;ull s;

ull a[MAXN];

vector<ll>g[1<<16][4];

ull G(ull x)

{

    x^=x<<13;

    x^=x>>7;

    x^=x<<17;

    return x;

}

inline ll ksm(ll b,ll p)

{

    ll cnt=1;

    while(p)

    {

        if(p&1)cnt=(ll)cnt*b%mod;

        b=(ll)b*b%mod;p=p>>1;

    }

    return cnt;

}

inline ll pd(ll x,ull ww)

{

	ull cc=a[x]^ww;

	ll cnt=0;

	while(cc)

	{

		++cnt;

		cc-=cc&(-cc);

		if(cnt>3)return 0;

	}

	return 1;

}

signed main()

{

    //freopen("1.in","r",stdin);

    scanf("%lld%lld",&n,&m);scanf("%llu",&s);

    ull x=s;

	ll maxx=1<<16;--maxx;

    rep(0,n-1,i)

    {

		ull s=x;

		a[i]=x;

		rep(0,3,j)

		{

			ll ww=s&maxx;

			g[ww][j].pb(i);

			s=s>>16;

		}

		x=G(x);

    }

    ll cc=ksm(2,m-1);

    ll ans=0;

	rep(1,m,i)

	{

		ull x;

		scanf("%llu",&x);

		ull s=x;ll flag=0;

		rep(0,3,j)

		{

			ll ww=s&maxx;

			if(g[ww][j].size())

				rep(0,g[ww][j].size()-1,k)if(pd(g[ww][j][k],x)){flag=1;break;}

			s=s>>16;

			if(flag)break;

		}

		if(flag)ans=(ans+cc)%mod;

		cc=cc*INV%mod;

	}

    //rep(1,n-1,i)a[i]=G(a[i-1]);

    //rep(0,n-1,i)putl((ll)a[i]);

    putl(ans);

    return 0;

}