BZOJ——T 4563: [Haoi2016]放棋子

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

Sample Output

HINT

Source

错排公式（ f[i]=f[i-1]+f[i-2] ）* (i-1) + 高精度（压位）

 #include <cstdio>

 const int mod();

 const int N();

 const int P();

 int n;

 #define max(a,b) (a>b?a:b)

 struct Num {

     int num[];

 //    Num() { for(int i=1; i<N; ++i) num[i]=0; num[0]=1; }

     void print()

     {

         printf("%d",num[num[]]);

         for(int i=num[]-; i; --i)

             printf("%0*d",P,num[i]);

     }

 }ans[N];

 inline void Add(Num a,Num b)

 {

 //    ans[0]=Num();

     ans[].num[]=max(a.num[],b.num[]);

     for(int i=,x=; i<=ans[].num[]; ++i)

     {

         ans[].num[i]=a.num[i]+b.num[i]+x;

         if(ans[].num[i]>=mod)

         {

             x=ans[].num[i]/mod;

             ans[].num[i]%=mod;

             ans[].num[]=max(ans[].num[],i+);

         }

         else x=;

     }

     for(; !ans[].num[ans[].num[]]&&ans[].num[]; ) ans[].num[]--;

 }

 Num Mul(Num a,int x)

 {

     for(int ove=,i=; i<=a.num[]; ++i)

     {

         a.num[i]=a.num[i]*x+ove;

         if(a.num[i]>=mod)

         {

             ove=a.num[i]/mod;

             a.num[i]%=mod;

             a.num[]=max(i+,a.num[]);

         }

         else ove=;

     }

     for(; !a.num[a.num[]]&&a.num[]; ) a.num[]--;

     return a;

 }

 inline void read(int &x)

 {

     x=; register char ch=getchar();

     for(; ch>''||ch<''; ) ch=getchar();

     for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';

 }

 int Presist()

 {

 //    freopen("firstmeet.in","r",stdin);

 //    freopen("firstmeet.out","w",stdout);

     read(n);

     ans[].num[]=ans[].num[]=;

     ans[].num[]=; ans[].num[]=;

     for(int i=; i<=n; ++i)

     {

         Add(ans[i-],ans[i-]);

         ans[i]=Mul(ans[],i-);

     }

     ans[n].print();

     return ;

 }

 int Aptal=Presist();

 int main(){;}

棋子