#include <iostream>
#include <ctime>
using namespace std;

int power(int a, int b)
{
    int sum = a;
    while (b > 1)
    {
        sum *= a;
        --b;
    }
    return sum;
}

long long Derangement(long long n)
{
    if (n == 2)
        return 1;
    if (n == 1)
        return 0;
    else
        return (n - 1)*(Derangement(n - 1) + Derangement(n - 2));
}

long long Derangement2(long long n)
{
    if (n == 2)
        return 1;
    if (n == 1)
        return 0;
    else
        return (n*(Derangement2(n - 1)) + (long long)power(-1,n));
}

int main()
{
    long long n, t;
    clock_t startTime, endTime;
    cout << "请输入错排问题的参数n。" << endl;
    cin >> n;

    startTime = clock();//记录开始时间
    t = Derangement2(n);
    endTime = clock();    //记录结束事件
    cout << "排法一共有" << t << "种。" << endl;
    cout << "运算时间为：" << (double)(endTime - startTime) / CLOCKS_PER_SEC << "秒。" << ‘\n‘ << ‘\n‘;

    startTime = clock();//记录开始时间
    t = Derangement(n);
    endTime = clock();    //记录结束事件
    cout << "排法一共有" << t << "种。" << endl;
    cout << "运算时间为：" << (double)(endTime - startTime) / CLOCKS_PER_SEC << "秒。" << endl;
    //在time.h文件中定义了一个常量CLOCKS_PER_SEC，它用来表示一秒钟会有多少个时钟计时单元
    
    return 0;
}