题目分析

我们要求的是： [ \sum_{i=0}^{n-1} \sum_{j=0}^{m-1} \max(i \oplus j - k, 0) \mod p ] 其中 $\oplus$ 表示按位异或运算。

问题转化

设 $S = \sum_{i=0}^{n-1} \sum_{j=0}^{m-1} (i \oplus j)$
设 $C = \sum_{i=0}^{n-1} \sum_{j=0}^{m-1} [i \oplus j \le k]$

那么原式可以写成： [ \text{答案} = S - k \cdot C ] 因为： [ \sum \max(i \oplus j - k, 0) = \sum_{i \oplus j > k} (i \oplus j - k) = S - k \cdot C ]

数位DP思路

由于 $n, m, k$ 可能达到 $10^{18}$，我们需要用数位DP来处理。

定义状态：

• $f[pos][limN][limM][limK]$：考虑二进制前 $pos$ 位时，$i \oplus j$ 的总和
• $g[pos][limN][limM][limK]$：考虑二进制前 $pos$ 位时，满足条件的方案数

其中：

• $limN$：$i$ 是否还受到 $n-1$ 的限制
• $limM$：$j$ 是否还受到 $m-1$ 的限制
• $limK$：$i \oplus j$ 是否还受到 $k$ 的限制（用于计算 $C$）

状态转移

设当前位为 $bit$（从高位到低位），$nb = n-1$ 的当前位，$mb = m-1$ 的当前位，$kb = k$ 的当前位。

对于总和 $S$：

枚举 $i$ 的当前位 $x$（0或1），$j$ 的当前位 $y$（0或1）：

• 如果 $x$ 且 $limN$ 且 $nb=0$，不能选1
• 如果 $y$ 且 $limM$ 且 $mb=0$，不能选1

当前位的贡献是 $(x \oplus y) \cdot 2^{pos}$，乘以低位方案数，加上低位的总和。

对于计数 $C$：

枚举 $x, y$ 同上，但还要考虑 $limK$：

• 如果 $limK$ 且 $(x \oplus y) > kb$，不能选
• 如果 $limK$ 且 $(x \oplus y) = kb$，下一位继续受限制
• 如果 $limK$ 且 $(x \oplus y) < kb$，下一位不受限制

算法流程

1. 将 $n-1, m-1, k$ 二进制分解
2. 用记忆化搜索计算：
   • $S = f[0][1][1][0]$（计算总和时不受 $k$ 限制）
   • $C = g[0][1][1][1]$（计算计数时受 $k$ 限制）
3. 答案 = $(S - k \cdot C) \mod p$

代码实现细节

• 使用 long long 存储状态，注意取模
• 记忆化搜索时，状态用 pos, limN, limM, limK 表示
• 注意 $n-1, m-1$ 可能为负数的情况（当 $n=0$ 或 $m=0$ 时）

时间复杂度

数位DP的状态数是 $O(\log \max(n,m,k) \times 2^3) = O(60 \times 8)$，非常高效。

样例验证

以 $n=3, m=3, k=1$ 为例：

• 原始表格：

  0 1 2
  1 0 3
  2 3 0
  

• 减1后：

  max(0,0) max(0,0) max(1,0) = 0 0 1
  max(0,0) max(0,0) max(2,0) = 0 0 2  
  max(1,0) max(2,0) max(0,0) = 1 2 0
  

• 总和 = 0+0+1+0+0+2+1+2+0 = 6，符合输出。

总结

本题的关键在于：

1. 将 $\max(i \oplus j - k, 0)$ 转化为 $S - k \cdot C$
2. 使用数位DP同时计算异或和与方案数
3. 注意边界情况和取模运算

这种方法可以处理 $10^{18}$ 级别的数据，时间复杂度 $O(\log \max(n,m,k))$。