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) + 高精度(压位)
#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(){;}