UPD: Большое спасибо за помощь, наконец разобрался что к чему. Надеюсь, теперь это поможет кому-нибудь ещё.
Привет, Codeforces!
Помогите разобраться с алгоритмом.
Собственно задача Если коротко, то у нас есть два целых числа N и M, мы должны посчитать количество чисел, которые могут быть получены из числа N перестановкой цифр, и которые делятся на M.
Решение "в лоб" — просто пробежаться по всем перестановкам цифр числа N и проверить каждую. Это дает нам N! операций, что слишком медленно. Интуитивно понятно, что нам в любом случае прийдется проверить каждую из перестановок и я не могу понять, как мы этого избегаем.
Используем ДП с битовыми масками: dp[i][j] — количество чисел, полученных перестановкой некоторых цифр N(которые определены маской i), и остача от деления на M равна j. Например, N=12345, dp[01101][2] — количество чисел, сложенных из 2,3,5 (такие как 352), и остача от деления на М равна 2 (M=50, 352%50==2). Для каждой маски i мы пробегаемся(переменная k) по всем еще не использованным цифрам((i & 1<<k)==0) и добаляем их в конец каждой перестановки(i | 1<<k). У старой перестановки остаток j, у новой — (j*10+N[k])%M, где N[k] — k-я цифра N. Увеличиваем dp[i | 1<<k][(j*10+N[k])%M] на dp[i][j].
Вот код для лучшего понимания: 12205724 Заметки: timesRepeat используется, чтоб избавится от повторяющихся перестановок, которые возникнут если в N есть повторяющиеся цифры. (i||N[k]) для избавления от лидирующих нулей
Используя ДП, мы снизили сложность от N! до (2^N)*N, что позволяет нам сдать задачу.
Рассмотрим данное решение: выглядит так, что мы пробегаемся по всем возможным перестановкам. Например, маска 0110 может быть получена как 0100 добавить третюю цифру в конец или же к 0010 добавить вторую цифру в конец. Для каждой маски мы добавляем каждую цифру в каждое место. Я не пойму, как мы проделываем меньше работы, но рассматриваем все перестановки.
Возможно это очень глупо, но я никак не вьеду. Помогите разобраться и подскажите, когда мы можем использовать такой приём. Можем ли мы применять его для любых перестановок и задач над ними?
