A. Stickogon

code

B. A BIT of a Construction

我们一定可以将 $n$ 分成 $a,b$，使得答案最大化。

具体地，若 $n$ 二进制下某位原本为 $1$，则 $a$ 的这位为 $1$，否则借位，$a,b$ 都为 $1$。

例如 $n_{(10)}=1001_{(2)}$，则 $a=111,b=10$。

code

C. How Does the Rook Move?

对于每一回合，若 $r=c$ 则相当于 $n$ 减小 $1$，否则 $n$ 就减少 $2$。

设 $f_n$ 表示 $2n\times 2n$ 的棋盘，不能走对角线的最终的不同棋盘状态数量。

这相当于是让 $2n$ 个点两两匹配的方案数，观察最后两个点：

• 若这两个点匹配则方案数加 $f_{n-1}$；
• 否则，先将其余点匹配完成后，从 $n-1$ 队中挑出一对，答案加上 $2(n-1)f_{n-1}$。

于是得到 $f_n=(2n-1)f_{n-1}$，初始化 $f_0 = 1$。

于是有答案

$$ans=\sum_{k=0}^n \left( _{k}^{n} \right) f_{\frac{n-k}{2}} \times 2^{\frac{n-k}{2}}$$

code

D. A BIT of an Inequality

设 $s_x = a_1 xor a_2 xor … xor a_x$，

$x,y,z$ 成立当且仅当 $(s_z xor s_{x-1})$ 的第 $mx_y$ 位为 $0$，$mx_y$ 表示 $y$ 的最高位。

于是直接计算就可以。

code