UVa 10497

From Algorithmist
Jump to navigation Jump to search

10497 - Sweet Child Makes Trouble[edit]

Summary[edit]

This is a derangement problem. Standard combinatorics problem - hard part is finding the recurrence.

Explanation[edit]

Given n arrangements, we can look at it in the following way:

1 2 3 4 5 ... n

all in their original permutation. So how many ways are there to solve it?

There are two cases, looking at any one particular element:

  1. Swap this element with another element ways to do that, and take care of two elements.
  2. Put another element in this location. There are elements for that.

In the first scenario, and since there are ways, and it takes care of two elements, . In the second scenario, only that element is taken care of, so . Now sum the two scenarios, and you have .

Gotchas[edit]

  • Use BigNum. For the answer is huge.

Input[edit]

2
3
4
5
20
-1

Output[edit]

1
2
9
44
895014631192902121