Untitled

mail@pastecode.io avatar
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