e-olymp 8514. Never drink too much!

The task is taken from e-olymp

Task

Mahmoud together with his friends visited Georgia. They would stay in a hotel at Rustavelli. When the cowboys reached the hotel, they hung their hats in the entrance and settled in. The beer bottles on the table could not escape from Mahmoud’s attention when passing through the corridor. At the suggestion of Mahmoud, all the cowboys began drinking. They drank too much, thus none of them was mindful. Then they decided going downtown. On the way out, everyone had a hat on, but they mixed up the hats as they were so drunk.

The man who is able to have on his own hat while he is drunk is considered clever and who is not able to do so is considered stupid.

You are given the number of cowboys — n (including Mahmoud). You should find in how many ways the cowboys may have on the hats so that all of them are stupid. Two ways are considered different if there is at least one cowboy who has a hat in this case and another hat in the other case.

As the answer may become very large, you should output the result modulo [latex]10^9+7[/latex].

Input

Given the number of cowboys — [latex]n (1 \leq n \leq 10^7)[/latex].

Output

The answer to the problem as specified above.

Tests

Inputs Outputs
1
1 0
2
4 9
3
9 133349
4
555 335132588
5
10000000 824182295

Code

 

Solution

We have all possible permutations [latex]C_n^0 \cdot n![/latex] , minus one fixed (one of them is not stupid) we get [latex]C_n^0 \cdot n!-C_n^1 \cdot (n-1)![/latex] but we subtract for minimum fixed pair (two of them are not stupid) we need to add them [latex]C_n^0 \cdot n!-C_n^1 \cdot (n-1)! + C_n^2 \cdot (n-2)! [/latex] etc.

So the [latex]k[/latex] member is  [latex]C_n^k \cdot (n-k)! \cdot (-1)^k[/latex]

Let`s find the attitude of [latex]k[/latex] member to the previous one. It`s [latex]-k -1[/latex]

The last one will be [latex]1[/latex] or [latex]-1[/latex] it depends on parity of [latex]n[/latex].

First two are the same ( [latex]n![/latex] ) so we skip them, but in this case we need to check if [latex]n[/latex] equals [latex]1[/latex]

And next we make a loop to find the answer by multiplying start value and add it to the answer.

The complexity is [latex]O(n)[/latex]

Links

ideone
e-olymp

Руслан Масальский

Прикладная математика. Одесский национальный университет им. Мечникова

e-olymp 63. Анфиса и цветы

Задача. Анфиса и цветы

Условие задачи

 Мурзик одну из цветочных клумб сделал в виде шахматной доски размерами [latex]m[/latex] на [latex]n[/latex], в каждой клеточке которой растет какой-то цветок. Иногда на эту клумбу он выводит на прогулку Анфису (да, не удивляйтесь, они действительно друзья). Анфиса, начиная всегда с верхнего левого угла передвигается по клумбе к правому нижнему и собирает цветы, причем таким образом, чтобы каждый раз проходить новым маршрутом, а Мурзик на выходе вручает ей кусочек сыра.

Посчитать, какое наибольшее количество кусочков сыра получит Анфиса, если она все время старается сохранить как можно больше цветов. При каждом очередном своем проходе Анфиса обязательно должна собрать как минимум один цветок.

<

h4″>Входные данные

В одной строке заданы два числа m и n [latex]\left( n, 0 < m, n ≤ 2\cdot 10^9 \right)[/latex].

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

Вывести наибольшее количество кусочков сыра, которые может получить Анфиса.

Также условие задачи можно посмотреть здесь.

Реализация

Тестирование

Входные данные (m, n) Выходные данные
1 2, 3 3
2 3, 3 5
3 3, 4 7
4 4, 3 7
6 5, 7 25

Алгоритм решения

Задана цветочная клумба в виде шахматной доски размерами [latex]m[/latex] на [latex]n[/latex]. Очевидно, что количество цветов на данной клумбе равно [latex]m\cdot n[/latex]. Пусть Анфиса, совершая свое очередное передвижение, начиная с левого верхнего угла клумбы и направляясь к правому нижнему,  съедает latex\cdot(n-1)[/latex]  цветов, так как, согласно условию задачи, Анфиса обязательно должна собрать как минимум один цветок при каждом проходе. После каждого такого прохода на выходе она получает один кусочек сыра.

Следовательно, имеет место следующая формула: [latex]p=(m-1)\cdot(n-1)+1[/latex], где p — наибольшее количество кусочков сыра, которое может получить Анфиса. Действительно, если [latex]m=2[/latex], [latex]n=3[/latex], то получаем [latex]p=3[/latex].

Ссылка на засчитанное решение.

Для запроса на выполнение нажать здесь.