学步园

http://acm.hdu.edu.cn/showproblem.php?pid=2068

错排公式：f(i) = (i - 1) * [f(i-1) + f(i-2)]。

//错排
#include <stdio.h>

int main()
{
	double fac[26], staggered[26];
	int i, n;
	fac[0] = 1, fac[1] = 1, fac[2] = 2;
	staggered[0] = 1, staggered[1] = 0, staggered[2] = 1;
	for(i = 3; i < 26; i ++){
		fac[i] = i*fac[i-1];
		staggered[i] = (i-1)*(staggered[i-1]+staggered[i-2]);
//		printf("fac[%d] = %.lf\n", i, fac[i]);
	}
	while(scanf("%d", &n)&&n){
		double sum = 0;
		for(i = 0; i <= n/2; i ++){
			sum += fac[n]/fac[i]/fac[n-i]*staggered[i];
		}
		printf("%.lf\n", sum);
	}
	return 0;
}