
ZOJ Problem Set  2625
N people stand in a line, and we numbered them 1,2...n, and now you are asked to rearrange them. The ith people is considred in the front of the (i+1)th, after the rearrange, everyone the people in front of whom can not be the same one as before. How many different strategies you can do the rearrange. Input: Each test case just contains one integer, the number of people you have to rearrange. Output: The number of strategies you have to rearrange them, with the condition above. Sample Input: 3 4 Sample Output: 3 11 Author: ZHOU, Kai Source: ZOJ Monthly, November 2005 