2016HUAS_ACM暑假集训4D - 计数,排列

时间:2023-01-13 08:43:38

一个错排公式的基础应用。

大致题意:求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]);
    ;
}