1 Отредактировано Baur (2010-03-31 06:15:22)

Тема: acm.mipt.ru #140

Всем привет! Помогите разобраться с одним хитрым случаем в этой задаче: Дан порядковый номер числа каталана N(N<=5*10^5), необходимо посчитать его по модулю К (К не обязательно простое, к<=2*(10^9) ). Я решал так -
число каталана C(n) можно записать как дробь  a/b = c(n);
a=2n!; b=n!*n!*(n+1);
1)  Перепишем это в виде а = b*C(n) и возьмем обе части по модулю к
2)  Получим a%k = b%k*ans (ans = c(n)%k - это и есть ответ на задачу)
3)  chis = a%k и znam = b%k посчитаем одним циклом, не забывая на каждом шаге брать  chis,znam по модулю k
4)  Пришли к сравнению znam*ans==chis(mod k)
5) Поделим chis,znam,K на GCD(znam,K) - теперь znam и k взаимно просты и можно применить теорему Эйлера
znam^phi(mod)==1(mod K);
6) найдем ans - из пункта 4 - ans = chis* (1/znam) (mod K) ,
где 1/znam  = znam^(phi(mod K)-1) (см. пункт 5)
В степень возводим за логарифм, так как она может достигать 2*(10^9)
А теперь, собственно, хитрый случай: этот метод работает, когда chis!=0 && znam!=0, в противном случае возникает неопределенность вида 0*ans==0(mod K). Кажется, этого можно избежать, если заранее перед пунктом 3 сократить числитель и знаменатель на K (факторизовав К и применив формулу Лежандра)  - но как-то не кошерно ради одного случая писать отдельный код, да еще я не уверен на 100%, что это поможет. Кто-нибудь знает, как можно проще обойти этот случай?

2

Re: acm.mipt.ru #140

Я считал числа по формуле Catalan(n)  = C(2*n, n) / (n + 1) = (2n)! / (n! * (n + 1)!), где C(n,k) - биномиальный коэффициент

test

3 Отредактировано Baur (2010-03-31 06:16:35)

Re: acm.mipt.ru #140

alt пишет:

Я считал числа по формуле Catalan(n)  = C(2*n, n) / (n + 1) = (2n)! / (n! * (n + 1)!), где C(n,k) - биномиальный коэффициент

Я тоже считал по этой формуле(когда писал, что С(N)=a/b, я имел в виду a=2n!; b=n!*n!*(n+1)). Но посчитать в лоб, а потом взять по модулю не получится - факториал  слишком огромный получается. Поэтому и пришлось числитель и знаменатель считать отдельно по модулю, а потом уже делать все то, что я писал выше.

P.S Исправил свой первый пост, там действительно непонятно было, что переменные a и b означают.

4

Re: acm.mipt.ru #140

Надо разложить числитель и знаменатель на простые множители, разделить числитель на знаменатель, после чего перемножить все оставшиеся в числителе простые числа (по модулю).
Пример

С(3) = 6! / (3! * 4!) = (6 *  5 * 4 * 3 * 2) / ((3 * 2) * (4 * 3 * 2)) = (2 * 3 * 5 * 2 * 2 * 3 * 2) / ((3 * 2) * (2 * 2 * 3 * 2)) = (5^1 * 3^2 * 2 ^ 4) / (3^2 * 2 ^ 4) = 5 ^ 1

test

5

Re: acm.mipt.ru #140

А можно другим решением. http://e-maxx.ru/algo/modular_factorial

6

Re: acm.mipt.ru #140

e-maxx пишет:

А можно другим решением. http://e-maxx.ru/algo/modular_factorial

Как? Ведь модуль может быть довольно большим и не обязательно простой.

test

7

Re: acm.mipt.ru #140

Тогда да, с таким методом больше геморроя будет. Действительно, проще по степеням простых считать

8

Re: acm.mipt.ru #140

alt пишет:

Надо разложить числитель и знаменатель на простые множители, разделить числитель на знаменатель, после чего перемножить все оставшиеся в числителе простые числа (по модулю).
Пример

С(3) = 6! / (3! * 4!) = (6 *  5 * 4 * 3 * 2) / ((3 * 2) * (4 * 3 * 2)) = (2 * 3 * 5 * 2 * 2 * 3 * 2) / ((3 * 2) * (2 * 2 * 3 * 2)) = (5^1 * 3^2 * 2 ^ 4) / (3^2 * 2 ^ 4) = 5 ^ 1

Спасибо, сдал задачу. Но только разложил не числитель и знаменатель а число К(по модулю которого берем) на простые и ТОЛЬКО ЭТИ простые исключил сначала из знаменателя, а потом из числителя(так пошустрее будет;)). Ну а потом применил метод, который описал в своем первом посте (там как раз уже гарантированно не будет неопределенностей вида
0*ans=0(mod K))

9 Отредактировано redrolla (2011-12-16 16:32:43)

Re: acm.mipt.ru #140

Ребята, выручайте...
Написал программу, алгоритм таков:
1) вводим n и k
2) раскладываем числитель и знамененатель на простые и записываем их в 2 массива (индекс элемента - само число, число этой ячейке массива - степень нашего числа)
3) вычитаем из числителя - знаменатель, в итоге остается число, разложенное по степеням простых
4) по формуле C = C%k * i%k, где i - абсолютно каждое число из оставшегося массива

В итоге все работает хорошо и быстро. Но как бы не так... На тесте 9 получаю "Wrong Answer".
Не могу понять, где же закралась ошибка... Помогите пожалуйста!
тхт файлик:
http://narod.ru/disk/34566717001/%D1%82 … !.txt.html