UVa 10497

From Algorithmist

Contents 1 10497 - Sweet Child Makes Trouble 2 Summary 3 Explanation 4 Gotchas 5 Input 6 Output

[edit] 10497 - Sweet Child Makes Trouble

• http://acm.uva.es/p/v104/10497.html

[edit] Summary

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

[edit] Explanation

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 n - 1 ways to do that, and take care of two elements.
2. Put another element in this location. There are n - 1 elements for that.

In the first scenario, and since there are n - 1 ways, and it takes care of two elements, f(n) = (n - 1)f(n - 2). In the second scenario, only that element is taken care of, so f(n) = (n - 1)f(n - 1). Now sum the two scenarios, and you have f(n) = (n - 1)(f(n - 1) + f(n - 2)).

[edit] Gotchas

• Use BigNum. For N = 800 the answer is huge.

[edit] Input

2
3
4
5
20
-1

[edit] Output

1
2
9
44
895014631192902121