Задача
У Барыша есть $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$.