hdu 1465 不容易系列之一

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

今天立神和我們講了錯排，才知道錯排原來很簡單，從第n個推起：

當n個編號元素放在n個編號位置,元素編號與位置編號各不對應的方法數用M(n)表示,那么M(n-1)就表示n-1個編號元素放在n-1個編號位置,各不對應的方法數,其它類推.

　　第一步,把第n個元素放在一個位置,比如位置k,一共有n-1種方法;

　　第二步,放編號為k的元素,這時有兩種情況.1,把它放到位置n,那么,對于剩下的n-2個元素,就有M(n-2)種方法;2,不把它放到位置n,這時,對于這n-1個元素,有M(n-1)種方法;

　　綜上得到

　　M(n)=(n-1)[M(n-2)+M(n-1)]

　　特殊地，M(1)=0,M(2)=1

所以這時候看來這道題就是模版題，不過要注意精度的問題——int64

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <math.h>

int main()

{

?? ?int n;__int64 a[22];

?? ?a[1]=0;a[2]=1;

?? ?for(__int64 i=3;i<=22;++i)

?? ?{

?? ? ? ? ? ?a[i]=(i-1)*(a[i-1]+a[i-2]);

?? ?}

?? ?while(scanf("%d",&n)!=EOF)

?? ?{

?? ? ? ? ? printf("%I64d\n",a[n]);

?? ?}

?? // system("pause");

?? ?return 0;

}