题解

思路推导

从高位到低位比较按位与和按位异或。设 $p=2^{n-1}$。

当 $n$ 为奇数时，一位上两者相等的方案数为 $p+1$：偶数个一且不全为一时两者均为零，全为一时两者均为一。不存在在该位首次变成“与大于异或”的方案，所以全部 $k$ 位都必须相等，答案为 $(p+1)^k$。

当 $n$ 为偶数时，一位上保持相等的方案数为 $p-1$；全为一是唯一让按位与在当前最高不同位胜出的方案。一旦胜出，所有更低位可任意选择。

做法

奇数 $n$ 直接快速幂。偶数 $n$ 令 answer=1、free=1，依次加入一个更高位：

迭代 $k$ 次即可。answer 的第一项表示新高位继续相等，第二项表示新高位由全一方案首次胜出、低位任意。

极小规模可枚举全部 $2^{nk}$ 个数组。独立核验程序按一位中一的个数枚举组合数，维护“已经胜出、仍相等、已经失败”三种比较状态。

正确性证明

整数比较由最高不同位决定。上述分类完整枚举了一位上按位与和按位异或的三种比较关系，并且各元素不同位的选择相互独立。

奇数 $n$ 时没有首次胜出的单比特方案，只有每位保持相等的数组获胜，因此乘法原理给出 $(p+1)^k$。

偶数 $n$ 时，加入新最高位后，原来已在低位获胜的方案只有在新位相等时仍获胜，共乘 $p-1$；新位全为一时立即胜出，全部低位共有 $2^{ni}$ 种。递推恰好覆盖且不重复所有获胜数组。故算法正确。

复杂度分析

每个测试用例时间复杂度为 $O(k+\log n)$，空间复杂度为 $O(1)$。