Здравствуйте. Дорешиваю задачи с полуфинала республиканской олимпиады, но одну задачу никак не могу решить. Подскажите пожалуйста, как решить эту задачу.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3740 |
3 | Radewoosh | 3652 |
4 | Benq | 3626 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3587 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3485 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 163 |
2 | maomao90 | 160 |
3 | adamant | 156 |
4 | atcoder_official | 155 |
5 | nor | 154 |
6 | cry | 153 |
7 | -is-this-fft- | 152 |
8 | maroonrk | 151 |
9 | SecondThread | 148 |
10 | Petr | 146 |
Название |
---|
for (x = 'a'; x <= 'z'; ++x) f[1][((0 * 3) ^ x) % D]++;
for (i = 1; i < n; ++i) for (j = 0; j < D; ++j) for (x = 'a'; x <= 'z'; ++x) f[i + 1][((j * 33) ^ x) % D] += f[i][j];
f[i][j] — количество слов длиной i и значением функции j. Будем приписывать к нему букву x. тогда из каждого такого слова f[i][j] получим слово длины i + 1 и со значением функции ((j * 33) ^ x) % D.
ответом будет f[n][k], да.
все отлично, но не так просто
сложность твоего решения n*D*26 = (10)*(2^25)*(26) а это довольно много
да и в память не влезает, даже если только последний слой хранить.
Мне кажется, что можно решить следующим образом.
Если M <= 20, то можно посчитать предложенную выше динамику: f[length][hash] — кажется решение за O(N * K * 2^M) (K — размер алфавита) успеет при данном дополнительном ограничении.
В ином случае проделаем следующие шаги (я не уверен, что они корректны при M <= 20):
Заметим, что 33 = 32 + 1 = 2^5 + 2^0 = (1 << 5) + 1. То есть 33 * x = (x << 5) + x.
Также обратим внимание, что все коды символов занимают не более 5 битов, откуда:
33 * hash(word) XOR ord(letter) = ((hash(word) << 5) + hash(word)) XOR ord(letter) = (hash(word) << 5) + (hash(word) XOR ord(letter)),
то есть XOR влияет только на последние 5 битов хеша.
Так как 33 и 2^M взаимно просты, то мы умеем обращать вычисление хеша (правда только по модулю):
hash(word) = (hash(word + letter) XOR ord(letter))* 33^{-1},
где 33^{-1} — обратный элемент к 33 по модулю 2^M.
Сначала посчитаем, сколько слов из (N — 5) букв имеют тот или иной хеш, это опять же можно сделать просто перебором всех слов за 26^(N — 5). Так как N <= 10, то 26^(N — 5) — не более, чем порядка 10^7 состояний.
После этого переберем последние 5 букв слова, для каждого набора посчитаем хеш префикса, если хеш всего слова был тем, что нам дали во входных данных — состояний будет 26^5, а это, как указывалось выше, порядка 10^7. Для каждого полученного хеша ответ увеличится на количество префиксов длины (N — 5), имеющих такой хеш — а это мы посчитали заранее.
то есть XOR влияет только на последние 5 битов хеша.
мне кажется что это не так Число может выйти за модуль после XOR и тогда там будет непонятно что, правильнее вроде бы сказать XOR влияет на последние 5 бит 33 * hash(word) а не всего хеша
Там модуль 2^M, а когда ты берешь по такому модулю остаются только M младших бит. разве нет?
Да, эта задача была когда-то давно в Coci (2014 год, март, 6 задача). Моё решение http://ideone.com/eJ3mWJ использует в целом эту же идею.
Интересно, что на COCI у этой задачи единственной из всего контеста было ограничение по памяти в 256 MB, а по предложенной выше ссылке ограничение стоит в 32 MB.
В связи с этим мне видится следующее уменьшение используемой памяти: для M = 25 все слова длины 5 имеют свой уникальный хеш (что очевидно, ведь 2^5 > 26), поэтому для этого случая можно при генерации хешей из первых 5 символов хранить не количество слов с таким хешем, а просто "было ли слово с таким хешем". Это можно сделать с помощью битсета, чем мы резко сократим память: с 2^25 байт (если считать, что мы хранили количество в однобайтном типе) до 2^25 / 32 или 2^25 / 64 байт в зависимости от реализации битсета.
Для 21 <= M <= 24 можно сделать аналогично: мы будем хранить 26 — M битсетов, в битсете b[i] для хеша H хранить бит b[i][H] == 1 только тогда, когда i-ый бит количества слов с хешом H будет равен 1. Таким образом, мы сможем вычислять количество слов с заданным хешом за 26 — M <= 5, а памяти будет тратиться не более, чем 2^M / 32 * (26 — M) — опять же не превысит 2^25 / 32.
Для M <= 20 можно будет также посчитать динамику просто, не парясь о памяти или времени.