Задача с тренировок Itmo

14 лет назад, # ^ |

Более точную оценку можно получить по неравенству Адамара
$\text{[math]}$
Когда N - степень двойки, она точная.
Пример матрицы строится рекурсивно.
A₁ = (P)
$\text{[math]}$
Если N не степень двойки, то эта оценка все равно очень близка к истине. Для этой задачи она дает 10⁷⁰⁰, мне удалось построить пример где-то на 10⁶⁹² и он есть в тестах. То есть по количеству цифр близко, но по отношению, конечно далеко. Но я уверен, что можно построить и лучший пример.

→ Ответить

Lepetrandr

14 лет назад, # |

Подскажите пожалуйста как решать задачу H "Сумма произведений" с тренировки 5 октября. Я просто двигал этот перемножающий отрезок домножая с одного края и деля с другого, и складывал текущие результаты. Делил расширенным Евклидом, получил TLE 19.

→ Ответить

Seyaua

14 лет назад, # ^ |

Немного поэкспериментировав, можно заметить следующую формулу, которая очевидным образом доказывается по индукции.

Собственно, формула для подсчета этой суммы, если a=1, b=x.

1*2*...*n+...+x*(x+1)*...*(x+n-1)=(x*(x+1)*...*(x+n))/(n+1).

Понятно, что в числителе (n+1) число => одно из них делится на (n+1), тогда его можно сразу поделить, а все остальное просто перемножить и посчитать по модулю. Тогда ответ получается как разность ответов для случаев a1=1, b1=b и a2=1, b2=a-1.

→ Ответить

indy256

14 лет назад, # ^ |

Можно в лоб, но главное чтоб без делений Евклидом.

Очевидно как посчитать два соседних произведения только через умножения, используя их перекрываемость.

Обобщив идею, можно рассчитывать n соседних произведений за 2*n умножений.

Становимся в позицию a+n и считаем n произведений влево и право: left и right.

Очередное произведение находится по формуле: left[i]*right[n-i]

Переходим к позиции a+2*n. И т.д.

→ Ответить

Gerald

14 лет назад, # ^ |

+10

Данная последовательность произведений, есть не что иное как сумма убывающих факториальных степеней

xⁿ= x * (x - 1) * (x - 2) * ... * (x - n + 1)

aⁿ + (a+1)ⁿ + (a+2)ⁿ + ... + (b+1)ⁿ = (bⁿ⁺¹-aⁿ⁺¹) / (n+1)

В Грекхеме подробно написано доказательство этого факта, да и в любой книжке я думаю в которой рассматривается теория конечных разностей

→ Ответить

mmaxio

14 лет назад, # |

На этой тренировке была еще одна задача(которую никто не решил). Сводилась она к извлечению квадратного корня из числа порядка 10¹⁰⁰⁰⁰⁰. Не знает ли кто-нибудь её решения?

→ Ответить

volkhin

14 лет назад, # ^ |

дихотомия + фурье не пройдет?

→ Ответить

ilyakor

14 лет назад, # ^ |

Что именно вы имеете в виду? Бинпоиском искать ответ и возводить в квадрат Фурье? Тогда вряд ли пройдёт, учитывая, что это n²log(n) (тем более, что можно сделать просто за квадрат безо всякого Фурье, но и такое проходить не должно). Или вы хотите как-то по-умному?

→ Ответить

volkhin

14 лет назад, # ^ |

Да, именно так - дихотомия по ответу, возведение в квадрат фурье и сравнение с числом. Для дихотомии можно задать хорошие границы - что то вроде от n >> (bitlength(n) + 3) до n >> (bitlength(n) - 3).

Я не совсем понял, откуда n^2log(n). Одно возведение в квадрат за nlog(n), возведений будет немного (< 20), если моя оценка на границы дихотомии верна.

→ Ответить

14 лет назад, # ^ |

Если в числе n знаков, то вообще бинпоиску надо будет O(n) итераций сделать. И, кажется, такие "умные" границы всё равно лишь вдвое уменьшат число итераций бинпоиска, или около того.

→ Ответить

volkhin

14 лет назад, # ^ |

Ок, увидел, что только вдвое.

→ Ответить

14 лет назад, # |

Какая именно это задача?

→ Ответить

14 лет назад, # ^ |

→ Ответить

14 лет назад, # ^ |

это же определитель.

откуда там извлечение корня?

→ Ответить

14 лет назад, # ^ |

А, сорри, промахнулся с деревом комментов :)

С корнем - не помню номер, но суть - про "? 1 ? 2 ... ? N = K". Там легко заметить, что при фиксированном N можно получить все K от -N(N+1)/2 до N(N+1)/2, но только той же четности, что и эти границы. В общем, если научиться быстро вычислять корень (ну и, пожалуй, быстро умножать два числа, но это боян), - тогда задача решена.

→ Ответить

14 лет назад, # ^ |

ну при условии что корень существует его за O(n) можно найти в принципе. но тоже работа с длинными числами.

→ Ответить

14 лет назад, # ^ |

Ну там надо так, что если корня нет, то подойдёт любое число в окрестности +-1 от корня :)

А как за O(n)? Что-то очень круто, быстрее даже, чем умножение двух длинных :)

→ Ответить

14 лет назад, # ^ |

← Rev. 2 →

сорри, перепутал с другим алго, глупость написал.

я вот думаю, число знаков мы может оценить в корне точно. и если по ним уже пускать дихотомию с умножением?

→ Ответить

ilyakor

14 лет назад, # ^ |

Очевидно же, что это вам почти не даст ускорения - чисел с данным количеством цифр тоже O(n).
Я вот думаю, может, её предполагалось за квадрат запихивать (особенно если учесть, что в другой задаче этого контеста с числами размера 100000 у нас квадрат прошёл)?

→ Ответить

14 лет назад, # ^ |

возможно и так.

меня гораздо более интересует решение задачи про количество красивых функций.

Если рассмотреть всевозможные степени перестановок, то очевидно, что при возведении в какую-то степень количество различных перестановок будем уменьшаться только если у нас степень d не взаимно проста с модулем K, где за K обозначим максимальную возможную степень + 1

правильный ли это подход?

→ Ответить

14 лет назад, # ^ |

А что за метод такой - за чистый квадрат, без логарифмов?

→ Ответить

14 лет назад, # ^ |

← Rev. 2 →

насколько я понимаю, с длинными все равно вылезет логарифм

за квадрат есть чистый метод нахождения корня

→ Ответить

KADR	14 лет назад, # ^ \| +3 http://wapedia.mobi/ru/%D0%9A%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D1%82%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D1%80%D0%B5%D0%BD%D1%8C#6. Внизу страницы есть метод. Вроде работает квадрат. → Ответить

taras.klaskovsky

14 лет назад, # |

Интересно, как решать I(сумма различных делителей).

→ Ответить

alexey.enkov

14 лет назад, # ^ |

← Rev. 4 →

Несложно доказать, что если N = p₁^a₁ * p₂^a₂ * ... * p_n^a_n, то можно представить все натуральные числа от 1 до $\text{[math]}$ , где k - минимальное такое, что выполняется $\text{[math]}$ (или k = n, если такое не выполняется)

Значит задачу можно решить так: раскладываем N на простые делители (стандартно пробегом до корня из N) и поддерживаем максимальное число, которое можем получить из уже найденных делителей. Таким образом либо разложим N полностью, либо поймём, что следующий простой делитель больше чем текущее максимальное число.

→ Ответить

Jughead

14 лет назад, # ^ |

А не можешь показать доказательство формулы?

→ Ответить

alexey.enkov

14 лет назад, # ^ |

Если p1 > 2, то ответ 2.

Пусть N = 2^a₁p₂^a₂...p_n^a_n. Понятно, что числа от 1 до $\text{[math]}$ можно представить в виде суммы различных делителей. (Используя только степени двойки).
Если M₁ < p₂ - 1, то понятно, что число M₁ + 1 представить не получится.
Пусть M₁ ≥ p₂ - 1. Пусть x = x₀ + p₂x₁ + p₂² x₂ + ... + p₂^a₂x_a₂, где x_i ≤ M₁, тогда x_i можно представить в виде суммы различных делителей числа N₁ = 2^a₁, значит и x можно. Таким образом можно представить все числа от 1 до $\text{[math]}$ .

Дальше аналогично.

→ Ответить

14 лет назад, # |

← Rev. 2 →

+26

Вот ссылка на разбор всех задач этого контеста. (Я автор последних 4-х задач).
http://www.repetitor.ua/files/folders/8889/download.aspx
Эффективное вычисление корня из N за O(log²N) разобрано в лекции
http://www.repetitor.ua/files/folders/8890/download.aspx

→ Ответить

ilyakor

14 лет назад, # ^ |

Что-то ссылки не открываются :(
Значит, в задаче про корень предполагался таки квадрат от количества цифр? Зачем тогда надо было делать такие длинные числа? Чтобы все помучались с оптимальной реализацией? :)

→ Ответить

14 лет назад, # ^ |

← Rev. 2 →

Сейчас выложу куда-нибудь по-нормальному.

О корне.
Важно, что мы можем взять большое основание 10000, и искать очередную цифру за константу.
и квадрат здесь на самом деле от количества цифр корня, а не от числа, то есть это уже величина порядка 12500, что для квадратной сложности вполне нормально.

→ Ответить

http://files.mail.ru/FWFT9H

14 лет назад, # ^ |

→ Ответить