给定 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
最佳答案
天真的方法需要 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]
关于algorithm - 当N很大时,从1到N的所有数位的异或和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41196800/