Задача #5085

Комбинаторика

Сложнее ЕГЭ

(Д. Статный, М. Шагитов) Сколько существует восьмиразрядных чисел, записанных в тринадцатеричной системе счисления, которые содержат ровно 6 различных цифр и не более 2-х цифр А .

Новая

Введите ответ

Войдите, чтобы история ответов и статистика сохранялись.

Решение Нажми, чтобы открыть Нажми, чтобы скрыть

Ответ

298322640

from functools import *
#рекурсия считает количество цепочек из цифр
@lru_cache(None)
def f(k, ka, digits):
    #если цепочка длины 8 подходит под условие, то она засчитывается
    if k==8: return ka<=2 and len(digits)==6
    #если количество цифр А или цифр в числе превышает условие, цепочки прерываются
    if ka>2 or len(digits)>6: return 0
    #в цепочки меньшей длины добавляется ещё одна цифра, количество цепочек с данным началом суммируется 
    return sum( f(k+1, ka+(i=='A'), digits|{i}) for i in '0123456789ABC')

#Ответ - суммарное количество цепочек, не начинающихся с нуля
print(sum(f(1, i=='A', frozenset(i)) for i in '123456789ABC'))

Номер