4563: [Haoi2016]放棋子
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 172 Solved: 119
[Submit][Status][Discuss]
Description
给你1个N*N的矩阵，每行有1个障碍，数据保证任意两个障碍不在同1行，任意两个障碍不在同1列，要求你在
这个矩阵上放N枚棋子（障碍的位置不能放棋子），要求你放N个棋子也满足每行只有1枚棋子，每列只有1枚棋子
的限制，求有多少种方案。
Input
第1行1个N，接下来1个N*N的矩阵。N<=200,0表示没有障碍，1表示有障碍，输入格式参考样例
Output
Sample Input
2
0 1
1 0
Sample Output
1
实际上就是1个错排计数，和障碍在哪儿没关系。
错排公式是f[i]=(f[i⑴]+f[i⑵])*(i⑴)，然后加1个高精度就行了。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define N 100000
using namespace std;
int n,now;
struct bignum
{
int l,a[N];
friend bignum operator +(bignum x,bignum y)
{
int t=max(x.l,y.l);
F(i,1,t) x.a[i]+=y.a[i];
F(i,1,t⑴) x.a[i+1]+=x.a[i]/10,x.a[i]%=10;
while (x.a[t]>=10) x.a[t+1]=x.a[t]/10,x.a[t]%=10,t++;
x.l=t;
return x;
}
friend bignum operator *(bignum x,int y)
{
int t=x.l;
F(i,1,t) x.a[i]*=y;
F(i,1,t⑴) x.a[i+1]+=x.a[i]/10,x.a[i]%=10;
while (x.a[t]>=10) x.a[t+1]=x.a[t]/10,x.a[t]%=10,t++;
x.l=t;
return x;
}
}a[2];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=⑴;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main()
{
n=read();
F(i,1,n) F(i,1,n) now=read();
if (n==1){puts("0");return 0;}
if (n==2){puts("1");return 1;}
a[0].l=1;a[1].l=1;a[1].a[1]=1;now=1;
F(i,1,n) now^=1,a[now]=(a[0]+a[1])*(i⑴);
D(i,a[now].l,1) printf("%d",a[now].a[i]);
printf("\n");
return 0;
}