[HAOI2016]放棋子(错排+高精度)

f[n] = (f[n-1] + f[n-2])*(n-1)
f[1] = 0
f[2] = 1

#include<bits/stdc++.h> 
#define N 205
using namespace std;

int n;

struct BigInteger{
    vector<int> a;
    BigInteger(){ a.clear(); }
    BigInteger operator = (long long num){
        a.clear();
        do{
            a.push_back(num % 10);
            num /= 10;
        }while(num);
        return *this;
    }
    BigInteger operator + (const BigInteger& B) const{
        BigInteger C;
        for(int i = 0, g = 0; ; i++){
            if(g == 0 && i >= a.size() && i >= B.a.size())  break;
            int x = g;
            if(i < a.size())    x += a[i];
            if(i < B.a.size())  x += B.a[i];
            C.a.push_back(x % 10);
            g = x / 10;
        }
        return C;
    }
    BigInteger operator * (const BigInteger& B) const{
        BigInteger C;
        C.a.resize(a.size() + B.a.size());
        for(int i = 0; i < a.size(); i++){
            int g = 0;
            for(int j = 0; j < B.a.size(); j++){
                C.a[i+j] += a[i] * B.a[j] + g;
                g = C.a[i+j] / 10;
                C.a[i+j] %= 10;
            }
            C.a[i+B.a.size()] = g;
        }
        while(C.a.size() > 1 && C.a.back() == 0)    C.a.pop_back();
        return C;
    }
}f[N], t;

void print(BigInteger x){
    for(int i = x.a.size() - 1; i >= 0; i--)
        printf("%d", x.a[i]);
}

int main(){
    cin>>n;
    f[1] = 0ll,;
    f[2] = 1ll;
    for(int i = 3; i <= n; i++){
        t = i - 1ll;
        f[i] = (f[i-1] + f[i-2]) * t;
    }
    print(f[n]);
    return 0;
}