virus_1010's blog

A Xor Problem
By virus_1010, history, 8 years ago, In English

Given T(1 <= T <= 1e5) the no. of test cases.
Each testcase contains an integer N(1 <= N <= 1e18).
We define F(x) as the xor of all the digits in x.
Find (summation of F(x) where x goes from 1 to N) for each testcase.
Can anyone help me with this?

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by virus_1010 (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by virus_1010 (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
← Rev. 6   Vote: I like it +2 Vote: I do not like it

simple digits dp — xor of digits <= 15. So dp[l][y][z][x] = number of len-(l+1) numbers, y denotes if number is non-prefix or not, z if number is non-zero or not, x the current xor — try current digit(c) 0-9(check c's possibility — (y||(c<=N[l])) then add dp[l-1][y||(c<N[l]][z||c][x^c]; write proper base cases.
For final answer, add (number of numbers for each xor<=15) * xor.

Time complexity — O(log(N)*64);

→ Reply