题目描述
给你一个N*N的矩阵，每行有一个障碍，数据保证任意两个障碍不在同一行，任意两个障碍不在同一列，要求你在这个矩阵上放N枚棋子（障碍的位置不能放棋子），要求你放N个棋子也满足每行只有一枚棋子，每列只有一枚棋子的限制，求有多少种方案。
输入输出格式
输入格式：
第一行一个N，接下来一个N*N的矩阵。N<=200,0表示没有障碍，1表示有障碍，输入格式参考样例
输出格式：
一个整数，即合法的方案数。
输入输出样例
输入样例#1：
20 11 0
输出样例#1：
1
/* 错排公式+压位高精（压了4位） 错排公式f(n)=(n-1)*(f(n-1)+f(n-2))*/#include#include #include #include using namespace std;#define maxn 5010int a[10000],b[10000],c[10000];int n,m,map[maxn][maxn];struct node{ int zu[10000],len; node operator + (const node x)const{ memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); for(int i=len,j=1;i>=1;i--,j++)a[i]=zu[j]; for(int i=x.len,j=1;i>=1;i--,j++)b[i]=x.zu[j]; int l=max(len,x.len); for(int i=1;i<=l;i++){ c[i]+=a[i]+b[i]; c[i+1]+=c[i]/10000; c[i]=c[i]%10000; } while(c[l+1]){ l++; c[l+1]+=c[l]/10000; c[l]=c[l]%10000; } node res; res.len=l; for(int i=1,j=l;i<=l;i++,j--)res.zu[i]=c[j]; return res; } node operator * (const int x)const{ memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for(int i=1,j=len;i<=len;i++,j--)a[i]=zu[j]; for(int i=1;i<=len;i++){ b[i]+=a[i]*x; b[i+1]+=b[i]/10000; b[i]=b[i]%10000; } int l=len; while(b[l+1]){ l++; b[l+1]+=b[l]/10000; b[l]=b[l]%10000; } node res; res.len=l; for(int i=1,j=l;i<=l;i++,j--)res.zu[i]=b[j]; return res; }}f[maxn];int main(){ scanf("%d",&n); f[1].len=1,f[1].zu[1]=0; f[2].len=1,f[2].zu[1]=1; for(int i=3;i<=n;i++) f[i]=(f[i-1]+f[i-2])*(i-1); printf("%d",f[n].zu[1]); for(int i=2;i<=f[n].len;i++)printf("%04d",f[n].zu[i]); return 0;}