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