Description:


Input:


第一行一个正整数,表示数据组数据 ,接下来T行
每行一个正整数N

Output:


2*T行
第2*i-1行表示第i个数据中问题一的解,

第2*i行表示第i个数据中问题二的解,

Sample Input:


Sample Output:


题解:


这一题比较妙~

因为 \(X\ xor\ 3X = 2X\) ,异或既可以当做不进位加法,也可以当做不进位减法,所以转换为 \(X\ xor\ 2X = 3X\) ,而 \(2X\)\(X\) 左移一位的结果,所以只要 \(X\) 满足不存在相邻的1就可以了。

那么第一问就变成了一个简单的数位DP。

因为第二问中 \(2^n\) 等价于1左移n位,那么只要求后面n位不出现相邻的1就可以了,有DP方程 \(f[x][0] = f[x-1][1] + f[x-1][0]\)\(f[x][1] = f[x-1][0]\) 。考虑矩阵乘法加速,即有 \(\begin{vmatrix} f[i+1][0] \\ f[i+1][1] \end{vmatrix} = \begin{vmatrix} 1 & 1 \\ 1 & 0 \end{vmatrix} \times \begin{vmatrix} f[i][0] \\ f[i][1] \end{vmatrix}\) ,然后就没有了。

代码如下: