#P11760. [IAMOI R1] 智力检测

[IAMOI R1] 智力检测

题目背景

小 C 拉小 L 去见岳父岳母。

岳父岳母决定考验小 L 的智商,于是他们出了一道题。

题目描述

岳父给定一个下标从 11 开始的数组 aa,初始时 ai=2i1a_i = 2^{i-1}

岳母让小 L 对这个数组进行如下操作若干次:

ii 次操作中,选择两个数 ui,vi (2ui<vi)u_i,v_i\ (2 \le u_i<v_i),依次执行:

  • aviavi+aui+aui1a_{v_i} \gets a_{v_i}+a_{u_i}+a_{u_i-1}

  • auia_{u_i} \gets -\infty

  • aui1a_{u_i-1} \gets -\infty

对于第一次操作没有特殊限制,但对于之后的每一次操作,都必须保证 vi>vi1v_i > v_{i-1}

给出 TT 次询问,每次两个数 kkxx,请回答能否通过有限次操作,使 ak=xa_k = x

询问之间相互独立(即每次询问后应重置 aa 数组)。

输入格式

本题读入量较大,建议采用较快的读入方式。

输入共 T+1T+1 行。

第一行,一个正整数 TT,表示询问的次数。

接下来 TT 行,每行两个正整数 kkxx,表示一组询问。

输出格式

输出一行一个 01 串。

01 串的第 ii 位表示第 ii 个询问的答案:

  • 如果对于第 ii 个询问,答案是“能”,则 01 串的第 ii 位为 1

  • 如果对于第 ii 个询问,答案是“不能”,则 01 串的第 ii 位为 0

4
6 36
6 35
5 30
5 31
0101

提示

对于 100%100\% 的数据,1T5×1061\le T\le5\times10^61k601\le k \le 600x4×10180\le x \le 4 \times 10^{18}

测试点编号 TT kk 特殊性质 分数
11 100\le100 10\le10 20
22 60\le60 60\le60 A
33 1×105\le1\times10^5 30
44 5×106\le5\times10^6

特殊性质 A:保证 x=2k1x=2^{k}-1

请注意您实现的常数复杂度。

时空限制均在标程(加快读优化)的 2.5 倍以上。

本题输入输出量较大,我们强烈建议您使用快速读入模板:

char *p1,*p2,buf[1<<20];
inline char gc(){if(p1==p2)p2=(p1=buf)+fread(buf,1,1<<20,stdin);return p1==p2?' ':*p1++;}
inline long long read(){
	register long long s=0; register char c=gc();
	while(c<'0'||c>'9') c=gc();
	while(c>='0'&&c<='9') s=(s<<3)+(s<<1)+(c^48),c=gc();
	return s;
}

x = read() //读入x