Задача
У Барыша есть $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 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> #include <cmath> using namespace std; int main() { int n,m,k; long long f=1,p=1000000007; cin >> n >> m; if (abs(n-m)>1) cout << "0"; else { k=min(n,m); for (int i=1; i<=k; i++) { f=f*i; if (f>=p) f=f%p; } f=f*f; if (f>=p) f=f%p; if (n==m) f=2*f; else f=f*max(n,m); if (f>=p) f=f%p; cout << f; } return 0; } |
Решение задачи
В данной задаче три случая. Если разница между количеством собак и обезьян превышает один, то будет невозможно разместить их так, чтобы собаки с обезьянами чередовались. Количество размещений собак равно $n!.$ Количество размещений обезьян равно $m!.$ Если количество одинаково, то сначала может быть как собака, так и обезьяна. Поэтому ответом будет $2n!m!$ и выведем ответ по модулю $10^{9}+7$. В остальных случаях будет ответом $n!m!$ и выведем ответ по модулю $10^{9}+7$. Последний случай, значит, что разница между количеством собак и обезьян это $1$. Промежуточные вычисления будут иметь тип long long, так как в промежуточных вычислениях, число может быстро увеличиваться. Поэтому после каждого умножения будем искать остаток при делении числа на $10^{9}+7$, если число будет превышать $10^{9}+7$.
У Вас 4 раза реализована одна и та же последовательность действий по вычислению факториала. Логично ее выделить в виде функции или по крайней мере (если Игорь Евгеньевич не требует здесь функций) избавиться от вычисления одного и того же в нескольких местах программы. Есть довольно очевидный способ обойтись ровно одним циклом вычисления факториала даже без функции. Прошу подумать об этом. К тому же, Вам повезло, что модуль p большой и простой, поскольку если бы в какой-то момент результат Ваших вычислений стал бы в точности равен p, он бы не обнулился.
Вы уменьшили количество циклов до двух. Это хорошо. Однако, если заметить, что факториалы считаются только при |n-m| <= 1, нетрудно обойтись одним циклом. И формально, раз мы берем по модулю p, условие должно быть if (f >= p) {..., хоть это и не влияет на ответ при данных ограничениях.
В строках 11-12 вы ищете минимум двух чисел, почему бы не воспользоваться функцией из cmath.
В цикле вы фактически находите $l!\cdot l!$, подумайте как уменьшить число операций.
Исправил.
min — не бесплатная операция и я очень сомневаюсь, что компилятор все соптимизирует до константы. Если Вам постоянно в цикле нужно искать min(m, n), я бы рекомендовал его посчитать один раз перед циклом.
К тому же, выражение f = f * i * (min(n, m) - i + 1) выглядит избыточным для поиска квадрата факториала. Не лучше ли посчитать факториал, а потом за одно действие возвести его в квадрат?
Владислав, вы учли замечание по поводу минимума, но посчитать факториал и возвести его в квадрат по прежнему не хотите. Это бы уменьшило число операций вдвое.
Понял, думал сначала как можно меньше ветвлений сделать.
Молодец!
В результате Вы оказались в таблице рекордов на первом месте.