一个错排公式的基础应用。
大致题意:求n个数的错误排列方式。(每个都要错)
在这里先贴一下错排公式:D(1)=0;D(2)=1;D(n)=(n-1)*(D(n-1)+D(n-2))
它的推导也非常有意思,用的应该是递归的思想吧(个人猜测)。
Sample Input
2
3
Sample Output
1
2
这题注意两点:
1.长整型__int64或者long long
2.最好打一下表,防止超时
然后,然后就过了呗......
#include<iostream> #include<cstdio> using namespace std; int N; __int64 ans[]; //错排 D(1)=0;D(2)=1;D(n)=(n-1)*(D(n-1)+D(n-2)) void slove() { ans[]=; ans[]=; ;i<=;i++) ans[i]=(i-)*(ans[i-]+ans[i-]); } int main() { slove(); while(cin>>N) printf("%I64d\n",ans[N]); ; }