Untitled
unknown
plain_text
a month ago
1.2 kB
3
Indexable
Never
def count_palindromic_binary_numbers(N, K): MOD = 10**9 + 7 count = 0 for bits in range(1, N + 1): # Generate all possible first halves of the palindrome for first_half in range(2**(bits // 2)): # Convert the first half to binary and remove the '0b' prefix bin_first_half = bin(first_half)[2:] # Pad the first half with leading zeros if necessary bin_first_half = bin_first_half.zfill(bits // 2) # Create the palindrome by appending the reverse of the first half if bits % 2 == 0: palindrome = bin_first_half + bin_first_half[::-1] else: palindrome = bin_first_half + '0' + bin_first_half[::-1] # Convert the palindrome back to an integer and check if it's divisible by K num = int(palindrome, 2) if num % K == 0: count = (count + 1) % MOD # Add 1 to the count because 0 is also a valid palindrome return (count + 1) % MOD N = int(input()) K = int(input()) print(count_palindromic_binary_numbers(N, K))
Leave a Comment