组合数学-错排公式+高精度

在一个大小为N*N的棋盘上，放置了N个黑色的棋子。并且，对于棋盘的每一行和每一列，有且只有一个棋子。
现在，你的任务是再往棋盘上放置N个白色的棋子。显然，白色棋子不能与黑色棋子重合。在此基础上，放置的方式还需要满足：对于棋盘的每一行和每一列，有且只有一个白色棋子。
当然，放置的方式有很多种，你只需要输出不同的放置方案数即可。

Input

第一行包含一个正整数N。
接下来N行，每行N个整数用于描述棋盘。 0表示这个位置是空的，而1表示这个位置有一个黑棋子。

Output

一行一个整数，表示合法的放置方案数。

Sample Input

2
0 1
1 0

Sample Output

1

Data Constraint

对于20%的数据，满足N<=10。
对于60%的数据，满足N<=20。
对于100%的数据，满足N<=200。

解题思路

可以通过行列交换把黑棋都放在一条对角线上。问题就转化成了求错排方案数。直接用错排公式+高精度即可求解。

代码

#include
using namespace std;
struct BigNum{
    int len,a[1000];
    BigNum(){len=1;}; 
    BigNum(int _){a[1]=_;len=1;}
    BigNum operator+ (const BigNum &r) const{
        BigNum re=BigNum(0);
        re.len=max(len,r.len);
        for(int i=1;i<=re.len+1;++i)    re.a[i]=0;
        for(int i=1;i<=re.len;++i){
            if(i<=len)      re.a[i]+=a[i];
            if(i<=r.len)    re.a[i]+=r.a[i];
        }
        for(int i=1;i<=re.len;++i){
            if(re.a[i]/10){
                re.a[i]-=10;
                ++re.a[i+1];
            }
        }
        if(re.a[re.len+1])      ++re.len;
        return re;
    }
    BigNum operator* (const int &r) const{
        BigNum re=BigNum(0);
        re.len=len;
        for(int i=1;i<=re.len+1;++i)    re.a[i]=0;
        for(int i=1;i<=re.len;++i)      re.a[i]=a[i]*r;
        for(int i=1;i<=re.len;++i){
            if(re.a[i]/10){
                re.a[i+1]+=re.a[i]/10;
                re.a[i]%=10;
            }
        }
        while(re.a[re.len+1]){
            ++re.len;
            if(re.a[re.len]/10){
                re.a[re.len+1]+=re.a[re.len]/10;
                re.a[re.len]%=10;
            }
        }
        return re;
    }
    void print(){
        for(int i=len;i>=1;--i)     printf("%d",a[i]);
        printf("\n");
    }
}D[205];
int main(){
    int n;
    scanf("%d",&n);
    D[1]=BigNum(0);D[2]=BigNum(1);
    for(int i=3;i<=n;++i)   D[i]=(D[i-1]+D[i-2])*(i-1);
    D[n].print();
    return 0;
}