Is starting right now.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
Название |
---|
Что и как нужно перебирать в 500?
Феерический челенж, не могу это не запостить
Код c175353 (он красный) по 250:
Читаю, вижу что на одну '1' он ответит 1 вместо 2, челенжу — unsuccessful. И так ещё двое в моей комнате челенжат, видимо по тому же тесту.
Потом замечаю s.clear() и понимаю что эта штука ВСЕГДА отвечает 2 :)
Обидно, упали и 250 и 500. Вдвойне обидно что дописал 1000 через 5 минут после конца
Решение третьей.
Напомню условие: N!k = N!k - 1 * (N - 1)!k . Единички при N = 0, при k = 0 совпадает с N, из чего вытекает что k = 1 это обычный факториал. Если взять логарифм то формула расчёта будет как у Ckn + k. Посчитать число нулей на конец числа в системе счисления B, по модулю MOD.
Сначала посчитаем ответ для простого B. Всё можно раскрыть в произведением чисел. Понятно, что надо учитывать только вклад чисел делящихся на B. Посчитаем сколько раз число X = Bt * u меньшее N появится в произведении: по формулам нетрудно вывести, что это Ck - 1k - 1 + (n - X). При k = 1 (обычный факториал) каждая пара (t, u) даёт нам по единичке, получаем частный случай: N / B + N / B2 + N / B3 + ....
Будем перебирать t, сумма C-шек с разным u считается возведением матрицы в степень (k маленькое, в векторе храним C^i_k и сумму). Конечно, при этом придётся поизвращаться, формула там что-то типа
где A1 матрица для вычисления следующего слоя C-шек, а A2 та же матрица, только с прибавлением k-ой C-шки в ответ, а B1 = Bt.
Начальный вектор — (1, 0, 0, 0...) так как C00 = 1.
Итак, мы посчитали сумму C-шек, что есть количество ноликов в системе по базе B, если B простое. Остальные случаи:
Чтобы понятней было про КТО, вот кусок кода:
Авторское решение такое же, только вместо КТО можно было считать например для B=8 по модулю 3MOD и делить (просто div) в конце на 3.
"B=10 считаем как для B=2" — видимо как B=5.
А вообще там ещё один трюк был, который мы не стали использовать: матрица получается такая специфическая, что можно её за квадрат перемножать (соответственно для K по крайней мере вдвое больше спокойно работает).
Кстати у Макото другое, более интересное, решение.
Трюк? Да, понятно что там A[a][b] только от a-b зависит.
И понятно что это подсчёт суммы C-шек для разных Bt можно объединить с возведением в степень, код упростится.
Может кто-нибудь объяснить решение medium-а одним циклом (за O(n))?