CF1994G

CF1994G

因为异或每个位是独立的，只需要处理进位即可。

因此，考虑从低到高枚举每一位，记录进位个数，令 \(dp(i, j)\) 表示到第 \(i\) 位，进了 \(j\) 位的方案数。暴力枚举 \(0/1\) 转移即可。

时间复杂度：\(O(nk)\)。

这个“数位 DP” 稍微与众不同的是 DP 的顺序，告诉我们不是所有数位 DP 都是从高到低枚举的。