e-olymp 8595. Собаки и обезьяны

Задача

У Барыша есть $n$ собак и $m$ обезьян. Он хочет выстроить их в одну линию. Но он не хочет, чтобы в каком-либо месте стояло подряд две собаки или две обезьяны, потому что в таком случае они начинают драться. Сколько существует различных вариантов построения, таких чтобы ни обезьяны, ни собаки не дрались. Ответ выведите по модулю $10^{9}+7$. Имейте в виду, что собаки и обезьяны между собой различаются.

Входные данные

Два числа $n$ и $m$ $\left(1 \leq n, m \leq 10^{5}\right)$.

Выходные данные

Выведите количество различных вариантов построения обезьян и собак по модулю $10^{9}+7$.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 2 2 8
2 3 2 12
3 1 8 0
4 100000 100000 530123477
5 99999 100000 768947656

Код программы

Решение задачи

В данной задаче три случая. Если разница между количеством собак и обезьян превышает один, то будет невозможно разместить их так, чтобы собаки с обезьянами чередовались. Размещение собак равно n!. Размещение обезьян равно m!. Если количество одинаково, то сначала может быть как собака, так и обезьяна. Поэтому ответом будет 2*n!*m! и выведем ответ по модулю $10^{9}+7$. В остальных случаях будет ответом n!*m! и выведем ответ по модулю $10^{9}+7$. Последний случай, значит, что разница между количеством собак и обезьян это $1$. Промежуточные вычисления будут иметь тип long long, так как в промежуточных вычислениях, число может быстро увеличиваться. Поэтому после каждого умножения будем искать остаток при делении числа на $10^{9}+7$, если число будет превышать $10^{9}+7$.

Ссылки

Условие задачи на E-Olymp

Код программы на IdeOne

8 thoughts on “e-olymp 8595. Собаки и обезьяны

  1. У Вас 4 раза реализована одна и та же последовательность действий по вычислению факториала. Логично ее выделить в виде функции или по крайней мере (если Игорь Евгеньевич не требует здесь функций) избавиться от вычисления одного и того же в нескольких местах программы. Есть довольно очевидный способ обойтись ровно одним циклом вычисления факториала даже без функции. Прошу подумать об этом. К тому же, Вам повезло, что модуль p большой и простой, поскольку если бы в какой-то момент результат Ваших вычислений стал бы в точности равен p, он бы не обнулился.

  2. Вы уменьшили количество циклов до двух. Это хорошо. Однако, если заметить, что факториалы считаются только при |n-m| <= 1, нетрудно обойтись одним циклом. И формально, раз мы берем по модулю p, условие должно быть if (f >= p) {..., хоть это и не влияет на ответ при данных ограничениях.

  3. В строках 11-12 вы ищете минимум двух чисел, почему бы не воспользоваться функцией из cmath.
    В цикле вы фактически находите $l!\cdot l!$, подумайте как уменьшить число операций.

  4. min — не бесплатная операция и я очень сомневаюсь, что компилятор все соптимизирует до константы. Если Вам постоянно в цикле нужно искать min(m, n), я бы рекомендовал его посчитать один раз перед циклом.

    К тому же, выражение f = f * i * (min(n, m) - i + 1) выглядит избыточным для поиска квадрата факториала. Не лучше ли посчитать факториал, а потом за одно действие возвести его в квадрат?

Добавить комментарий