# UVa 10497

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:

- Swap this element with another element ways to do that, and take care of two elements.
- 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