sifat_15's blog

Lightoj 1021 — Painful Bases
By sifat_15, history, 7 years 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

»
7 years 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).

→ Reply
»
7 years 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

→ Reply
  • »
    »
    7 years 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?

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your code is so beautiful and self-explanatory. Thanks!

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Isn't the complexity of your code 2^N * N * K * T? Which is almost 2*10^9.

    How does it avoid TLE? :o

    The complexity of my code is same too. I coded with this logic because I had no option left during a practice contest. I was surprised to see this getting Accepted.

    Or am I missing something in this complexity calculation?

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    is rem * base always valid ie are all the digits of (rem*base) fall into 0 to base-1?

    → Reply