Codeforces Round #235 (Div. 2) — Problem D

Problem Statment

Given a set of digits [0–9] that form a number n < 10e18 and number “mod” m < 100 count the number of permutation of the given set of digits that has two features:

  • it doesn’t have any leading zeroes,
  • the remainder after dividing number x by m equals 0.

The solution exist in the input limits n < 10e18 thats mean you dealing with 18 digit number and that’s lead to a dynamic programming solution dp(mask , remainder_of the mod) to count all the possible permutations.

Here is my dp solution O((1<<|n|)*m) , |n| is the number of digits in the number n.

https://gist.github.com/Magdi/9475565


Originally published at mmagdi.com.