bzoj4563【HAOI2016】放棋子
來源：程序員人生 發布時間：2016-07-09 13:37:33 閱讀次數：2432次
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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
