【题解】智力检测
感谢出题人 Tian36309 写下了此篇题解的初版，并对修改版提出了宝贵的修改意见。
[IAMOI R1] 智力检测 题解
定义 I 定义“用
v 取a_u ”代表对u_i=u ，v_i=v 进行题目所述的操作定义 II 定义“
a_u 被取”表示对于某个v ，用v 取了a_u 命题 I 取数时，
a_u 不可能被重复取。
- 证明显然，反证法。考虑到如果取重复的
a_u 会取到-\infty ，你后面无论怎么取，都无法取回一个非负数。同时题目保证x 是个非负数，矛盾，所以不能重复取。
命题 II 如果
x < 2^{k-1} 或者x \ge 2^k ，那么本次询问无解。
-
根据命题 I，可以知道
a_u 不能重复取，这意味着每个操作的a_u 和a_{u-1} 均非负，也就是说，经过多次操作之后，a_k 必然只增不减，那么x<2^{k-1} 自然也就无解了。 -
继续根据命题 I，可以继续知道
a_u 不能重复取，注意到最极限的情况显然是通过反复操作把2^0 ，2^1 ，2^2 ，……，2^k 取一次，也就是说a_k \le 2^k-1 ，这显然不到2^k ，于是x\ge 2^k 无解。
以下的分析令
命题 III 可以通过若干次操作使
a_k = x ，当且仅当如果x 二进制下不包含连续奇数个1 。
-
由于
a 数组的特殊性质，我们把a 数组转换成二进制后发现，第一次取a_u 和a_{u-1} 就相当于把a_v 的第u 位和第u-1 位改为1 ，而下一次操作中选的数如果是a_v 则这次操作后那一个数的第u-1,u,v,v-1 位都将变为1 。 -
由于
u_i<v_i<v_{i-1} ，因此上述性质成立。 -
由于每次操作都是将两位改为
1 ，因此如果x 二进制下包含连续奇数个1 ，那么必然无法操作得到。
那么我们就有了第一个思路：
-
对于每一次询问，将
x 进行二进制拆分，如果发现存在连续奇数个1 输出0 ，否则输出1 。 -
单次询问
O(\log x) ，常数比较好的话可以获得90 分。（卡一卡没准可以拿满分）
命题 IV 对于每一个合法的答案（即不出现连续奇数个
1 ，后同），其一定是3 的倍数。
证明平凡，因为相邻两个
命题 V 对于每一个合法的答案，用它除以
3 后进行二进制拆分，一定不会出现连续的1 。
- 观察到，除以
3 相当于在除以(11)_2 ，试一下就会发现，二进制下连续偶数个1 除以(11)_2 就等于(1010101\ldots)_2 。 - 而若一个不包含连续
1 的二进制数乘3 ，结果中一定只包含连续的偶数个1 （相当于将其右移一位再相加）。 - 综上，得证。
命题 VI 符合是
3 的倍数和除以3 后进行二进制拆分，不会出现连续的1 的数必然是合法的答案。
- 显然，所有不含连续的
1 的二进制数乘三都是合法答案。
那么，我们只需要判断如下两个条件即可：
对于第二个条件，可以通过
时间复杂度
#include<bits/stdc++.h>
using namespace std;
long long T,k,sum,mi[100];
inline long long read()
{
char c=getchar();long long x=0,f=1;
for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=x*10+c-48;
return x*f;
}
int main(){
T = read();
mi[1] = 1;
for(int i=2;i<=62;i++)mi[i] = mi[i-1]*2;
while(T--){
k = read();
sum = read();
if(sum >= mi[k+1] or sum < mi[k]){
printf("0");
continue;
}
sum -= mi[k];
if(sum % 3 == 0 and (((sum/3) & (sum/3*2)) == 0))printf("1");
else printf("0");
}
return 0;
}