Тема: 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). То есть в целом алгоритм практически линейный. Вопрос в том это вообще корректно ? или может чего то проще есть?