Editing 1970 - secventa xor

==Enunţ==
Fie secvența S(x) care se construiește astfel:

S(1)=x
S(n+1)=S(n) XOR [S(n)/2], unde [x] se definește ca parte întreagă din x, iar XOR este operația clasică „sau exclusiv”.

==Cerința==
Dându-se un număr natural k, aflați numărul de numere naturale x pentru care S(k+1)=S(1)=x este adevărat. Deoarece numărul poate fi foarte mare, afișați rezultatul modulo 1000000007.

==Date de intrare==
Fișierul de intrare secventa.in se găsește un singur număr natural k.

==Date de ieșire==
Fișierul de ieșire secventa.out va conține pe prima linie un singur număr – răspunsul problemei modulo 1000000007.

Dacă pentru un număr k există o infinitate de numere x care respectă cerința, se va afișa numărul -1.

==Restricții și precizări==
*1 ≤ k ≤ 10^19

==Exemplul 1==
;secventa.in
:260

;secventa.out
:15

==Exemplul 2==
;secventa.in
:100000000000000000000

;secventa.out
:Date de intrare invalide!

==Rezolvare==
<syntaxhighlight lang="python" line>
#1970 secventa xor
MOD = 1000000007

def calculate_sequence_term(k, x):
  while k > 0:
    x = x ^ (x // 2)
    k -= 1
  return x

def count_matching_numbers(k):
  count = 0
  for x in range(1, k + 1):
    if calculate_sequence_term(k, x) == x:
      count += 1
  return count % MOD

def verify_input_data(k):
  if not (1 <= k <= 10 ** 19):
    with open("secventa.out", "w") as fout:
      fout.write("Date de intrare invalide!")
    return False
  return True

def main():
  with open("secventa.in", "r") as fin:
    k = int(fin.readline().strip())

  if not verify_input_data(k):
    return

  matching_numbers = count_matching_numbers(k)

  with open("secventa.out", "w") as fout:
    fout.write(str(matching_numbers))

if __name__ == "__main__":
  main()
</syntaxhighlight>