Cristina94: Pagină nouă: ==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 nu...

2024-04-01T14:10:56Z

Pagină nouă: ==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 nu...

New page

==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>

1970 - secventa xor - Revision history