Блог пользователя sifat_15

Lightoj 1021 — Painful Bases
Автор sifat_15, история, 7 лет назад, По-английски

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

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить