1 Тема от MSDN

  • MSDN
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-03-09
  • Сообщений: 40

Тема: timus 1747

Здравствуйте!

http://acm.timus.ru/problem.aspx?space=1&num=1747

Собственно задачу можно свести очевидно к такой - дан набор чисел, каждое число встречается 2 раза, нужно найти количество перестановок в которых два одинаковых числа не стоят подряд. У меня идея есть решать это формулой включений и исключений. В формуле присутствуют биномиальные коэффициенты. Все вычисления делаются по модулю, но он может быть не простым, поэтому вычисление бином. коэффициентов с использованием обратного элемента в кольце не катит. Также рекуррентная формула C[n][k]=C[n-1][k-1]+С[n-1][k] не катит , так как она за квадрат находит, а это долго в условиях данной задачи.
Есть идея воспользоваться китайской теоремой об остатках (алгоритм Гарнера). А именно разложить модуль на простые множители, для каждого простого модуля найти остатки и потом по ним восстановить остаток по исходному модулю. Модуль может быть до 10^9 поэтому различных простых множителей не больше 8. Алгоритм Гарнера работает за квадрат от количества простых множителей, ну и для каждого множителя нужно заполнить массив остатков за O(N). То есть в целом алгоритм практически линейный. Вопрос в том это вообще корректно ? или может чего то проще есть?

2 Ответ от MBo Отредактировано MBo (2010-06-07 08:51:55)

  • MBo
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-10-05
  • Сообщений: 52

Re: timus 1747

получилось вот такое рекуррентное соотношение
a[n] := n * (a[n - 1] * (2 * n - 1) + a[n - 2] * (n - 1))

3 Ответ от MSDN

  • MSDN
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-03-09
  • Сообщений: 40

Re: timus 1747

Спасибо. А можно если не трудно пояснить из каких соображений это вытекает?

4 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: timus 1747

Кстати, С(N,K) можно считать за O(N) без китайской теоремы об остатках. Достаточно просто разложить на простые множители числитель и знаменатель, и выполнить сокращение. Тогда останется только перемножить набор чисел по модулю P.

5 Ответ от MBo

  • MBo
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-10-05
  • Сообщений: 52

Re: timus 1747

К сожалению, это полуэмпирика.
Я исходил из таких соображений (видимо, дефективных):
Часть последовательностей P(n) можно построить из ''хороших" последовательностей P(n-1), вставив пару очередных чисел n в "дырки", часть из хороших последовательностей P(n-2), вставляя слитную пару чисел  n-1 вместе в одну дырку, одно число n для разбития пары в ее середину, и одно n в оставшиеся места, и часть из P(n-3), вставив две слитных пары (n-1) и (n-2), и оставшиеся числа n разбивают эти пары.
При этом концы с концами не сходились, но на нескольких первых членах заметил, что без P(n-3) можно обойтись, получив вышенаписанное соотношение, и проверил его для бОльших n.

6 Ответ от 2rf

  • 2rf
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-08-14
  • Сообщений: 42

Re: timus 1747

Я решил эту задачу именно как автор темы, прошло за 0.39. В формуле, котрую я использовал, было N членов и в каждом биномиальные коэффициенты, но при этом соседние члены несильно отличались, и я просто хранил текущий член, пересчитывал и прибавлял к ответу.