Rearrange Them

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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

题意：

      将n个数重新排列，使每个数的前一个数都不能和之前的一样，求有多少种满足的。

思路：

      状态转移方程为：f[i] = f[i-1]*(i-1)+f[i-2]*(i-2)。

      然后还要用大数写。

代码：

#include<stdio.h>
#include<string.h>
int n;
int f[110][210];
void dp(int a,int b,int c)
{
	int i,j,k;
	k=0;
	for(i=0;i<=200;i++)
	{
		j=b*f[b][i]+c*f[c][i]+k;
		f[a][i]=j%10;
		k=j/10;
	}
}
void DP()
{
	int i;
	memset(f,0,sizeof(f));
	f[0][0]=0;f[1][0]=0;
	f[2][0]=1;f[3][0]=3;
	for(i=4;i<=100;i++)
		dp(i,i-1,i-2);
}
int main()
{
	int i,j,k;
	DP();
	while(scanf("%d",&n)!=EOF)
	{
		if(n<2)
		{
			printf("0\n");
			continue;
		}
		for(i=200;i>=0;i--)
		{
			if(f[n][i]!=0)
				break;
		}
		for(j=i;j>=0;j--)
			printf("%d",f[n][j]);
		printf("\n");
	}
	return 0;
 }