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

题意：
给你一个N*N的矩阵，每行有一个障碍，数据保证任意两个障碍不在同一行，任意两个障碍不在同一列，要求你在这个矩阵上放N枚棋子（障碍的位置不能放棋子），要求你放N个棋子也满足每行只有一枚棋子，每列只有一枚棋子的限制，求有多少种方案。

思路： 假设我们把每行障碍上的那个元素 当做 元素本来就在的位置。

那么题意就是让其全部错位---没有一个元素是在他原本的位置上

我们处理这样一个数组f[n]表示n个数错排的方案数

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

由于n为200，并且题目没有要求取模，所以我们要需要敲一个高精度的板子。

code

#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;
}