Hello, Codeforces!

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[01101][2] — 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 dp[i][j].

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?