sifat_15's blog

By sifat_15, history, 18 months ago, In English,

Can Anyone give the idea for the following Problem LOJ — 1021 Painful Bases

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sifat_15 (previous revision, new revision, compare).

»
18 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Let dp[mask][rem] represent the number of permutations of the digits corresponding to the indices of set bits in the input string and having remainder rem when divided with k.

for all i such that i is not set in mask:
       dp[mask | (1 << i)][(rem * base + digit[i]) % k] += dp[mask][rem]

Code

Similar Problem

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't understand how the mask work here (I mean how do I get all the permutation)! please describe it a little bit more. And what would be the complexity of this code?