UPD: Thank you for your help, sort it out for myself. Hope this may help someone else now.
I ask you to help me understanding how does the algorithm work.
Here is the problem. Basically we have two integers N and M, we need to find how many numbers obtained by rearranging digits of N are divisible by M.
So naive solution is just go through all permutations of digits of N and check all of them. That gives us N! operations, which is unacceptably slow. Intuitively, we must go through all permutations anyway. And I am very confused about how do we not.
We use bitmask DP:
dp[i][j] — amount of numbers, obtained by permutation some digits of N(specified by bitmask i), and remainder after diving it by M is j. For example
N=12345, dp — amount of numbers, constructed with 2,3,5 (such as 352), and after division by M remainder is 2 (
M=50, 352%50==2). For each bitmask i we iterate(variable k) through all unused yet digits(
(i & 1<<k)==0) and add it to the end of every permutation(
i | 1<<k). Old permutations gave remainder j, now it will be
(j*10+N[k])%M, where N[k] is k-th digit of N. So we increase
dp[i | 1<<k][(j*10+N[k])%M] by
Here is the code to make it easier: 12205724 Note:
timesRepeat is used to eliminate duplicate permutations regarding repeated digits in N.
(i||N[k]) is to get rid of leading zeros
Using DP, we descend from N! to (2^N)*N, which gives us accepted.
Consider the solution: seems like we iterate through every permutation. For example, bitmask 0110 can be obtained as 0100 adding third digit to the end or 0010 adding second digit to the end. I cannot understand how are we doing less work, but logically we go over every permutation.
Maybe it is stupid question, but I am really confused. Please help me to sort it out and tell when do we use such method. Can we use it to any kind of permutations?