algorithm - 当N很大时，从1到N的所有数位的异或和

Question

给定 1 和 N ，我们需要求出从 1 到 N 的所有数位的异或值之和， 例如对于 N ，我们需要计算函数 F

F(k){
    ans =0;
    while(k>0){
      ans= ans^(k%10);
      k/=10;
   }
   return ans;
}

对于 [1,N] 中的 K。

有没有一种有效的方法来做 say . 据我所知，我们应该计算值 V 将使用 DP 进行异或的次数，但我想不出实现它的方法。

请给出一些想法。

示例:F (37) = 3 ^ 7 = 4

注意:N 可以大到 10^18

Answer 1

天真的方法需要 O(N*log10(N)) 时间，通过进行简单的优化，您可以获得 O(N) 运行时间。想法是:

第 k 个数字的所有数字的 XOR = 第一个 (k - 1) 个数字的 XOR ^ 最后一个数字。

显然，您可以通过将数字除以 10 来找到前 k - 1 位数字，因此关系变为:

F(i) = F(i/10) ^ (i % 10)

代码:

result = 0
for i = 1:N
  dp[i] = dp[i/10] ^ i%10
  result += dp[i]