Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

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

[SPOJ] LQDNUMS
Автор danhnguyen0902, 11 лет назад, По-английски

Does anyone know how to solve this problem?

http://www.spoj.com/problems/LQDNUMS/

Or at least please give me the references for it. Thanks a lot in advance.

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

»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I have some ideas to solve it in polynomial time, but it's too slow.
Let F(N) be the length of the result string. We have to find N, such that F(N) == M.
Use binary search to find N. F(N) can be calculated using DP and fast matrix exponentiation. I know how to do it with about 18-36 matrices of size K x K, K ~ 18 * 10 * 2.

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

    No, i was wrong with matrix exponentiation. I think there is kind of dp, we have to divide iterval [1..N] into several ones with the same prefix. for example for N = 1234 ther will be
    [1..999] for all numbers with length < length(N)
    [1000..1199] — 1 234
    [1200..1229] — 12 34
    [1230..1234] — 123 4

    for each of these intervals we have to use this dp recursively.

    → Ответить