Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 387 Solved: 247
[Submit][Status][Discuss]
Description
给你一个N*N的矩阵，每行有一个障碍，数据保证任意两个障碍不在同一行，任意两个障碍不在同一列，要求你在
这个矩阵上放N枚棋子（障碍的位置不能放棋子），要求你放N个棋子也满足每行只有一枚棋子，每列只有一枚棋子
的限制，求有多少种方案。
Input
第一行一个N，接下来一个N*N的矩阵。N<=200,0表示没有障碍，1表示有障碍，输入格式参考样例
Output
一个整数，即合法的方案数。
Sample Input
2
0 1
1 0
0 1
1 0
Sample Output
1
HINT
Source
错排公式（ f[i]=f[i-1]+f[i-2] ）* (i-1) + 高精度（压位）
1 #include <cstdio> 2 3 const int mod(10000); 4 const int N(5233); 5 const int P(4); 6 int n; 7 8 #define max(a,b) (a>b?a:b) 9 struct Num { 10 int num[10000]; 11 // Num() { for(int i=1; i<N; ++i) num[i]=0; num[0]=1; } 12 void print() 13 { 14 printf("%d",num[num[0]]); 15 for(int i=num[0]-1; i; --i) 16 printf("%0*d",P,num[i]); 17 } 18 }ans[N]; 19 inline void Add(Num a,Num b) 20 { 21 // ans[0]=Num(); 22 ans[0].num[0]=max(a.num[0],b.num[0]); 23 for(int i=1,x=0; i<=ans[0].num[0]; ++i) 24 { 25 ans[0].num[i]=a.num[i]+b.num[i]+x; 26 if(ans[0].num[i]>=mod) 27 { 28 x=ans[0].num[i]/mod; 29 ans[0].num[i]%=mod; 30 ans[0].num[0]=max(ans[0].num[0],i+1); 31 } 32 else x=0; 33 } 34 for(; !ans[0].num[ans[0].num[0]]&&ans[0].num[0]; ) ans[0].num[0]--; 35 } 36 Num Mul(Num a,int x) 37 { 38 for(int ove=0,i=1; i<=a.num[0]; ++i) 39 { 40 a.num[i]=a.num[i]*x+ove; 41 if(a.num[i]>=mod) 42 { 43 ove=a.num[i]/mod; 44 a.num[i]%=mod; 45 a.num[0]=max(i+1,a.num[0]); 46 } 47 else ove=0; 48 } 49 for(; !a.num[a.num[0]]&&a.num[0]; ) a.num[0]--; 50 return a; 51 } 52 53 inline void read(int &x) 54 { 55 x=0; register char ch=getchar(); 56 for(; ch>'9'||ch<'0'; ) ch=getchar(); 57 for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0'; 58 } 59 60 int Presist() 61 { 62 // freopen("firstmeet.in","r",stdin); 63 // freopen("firstmeet.out","w",stdout); 64 read(n); 65 ans[1].num[0]=ans[2].num[0]=1; 66 ans[1].num[1]=0; ans[2].num[1]=1; 67 for(int i=3; i<=n; ++i) 68 { 69 Add(ans[i-1],ans[i-2]); 70 ans[i]=Mul(ans[0],i-1); 71 } 72 ans[n].print(); 73 return 0; 74 } 75 76 int Aptal=Presist(); 77 int main(){;}