给你1个N*N的矩阵，每行有1个障碍，数据保证任意两个障碍不在同1行，任意两个障碍不在同1列，要求你在
这个矩阵上放N枚棋子（障碍的位置不能放棋子），要求你放N个棋子也满足每行只有1枚棋子，每列只有1枚棋子
的限制，求有多少种方案。
bzoj4563【HAOI2016】放棋子
发布时间：2020-12-13 21:11:01 所属栏目：PHP教程 来源：网络整理
导读：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枚棋
4563: [Haoi2016]放棋子Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 172 Solved: 119 [Submit][Status][Discuss] DescriptionInput第1行1个N，接下来1个N*N的矩阵。N<=200,0表示没有障碍，1表示有障碍，输入格式参考样例
Output
1个整数，即合法的方案数。
Sample Input
2
0 1 1 0 Sample Output1
实际上就是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,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,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,t) x.a[i]*=y;
F(i,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,n) F(i,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,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;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |