首页 > 代码库 > bzoj4563 [Haoi2016]放棋子
bzoj4563 [Haoi2016]放棋子
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
正解：组合数学+高精度。
因为每一行和每一列都只有一个障碍，所以不难发现行和列是可以交换的。
我们把障碍移动到主对角线上，发现答案就是错排公式。
$f[i]=(f[i-1]+f[i-2])*(i-1)$，直接递推即可，要写高精度。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue>10 #include <stack>11 #include <map>12 #include <set>13 #define inf (1<<30)14 #define il inline15 #define RG register16 #define ll long long17 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)18 19 using namespace std;20 21 int cnt[210],n;22 ll f[210][1010];23 24 25 il int gi(){26 RG int x=0,q=1; RG char ch=getchar();27 while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();28 if (ch==‘-‘) q=-1,ch=getchar();29 while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();30 return q*x;31 }32 33 il void work(){34 n=gi(),f[2][0]=1;35 for (RG int i=3;i<=n;++i){36 cnt[i]=cnt[i-1];37 for (RG int j=0;j<=cnt[i];++j)38 f[i][j]+=f[i-1][j]+f[i-2][j],f[i][j+1]+=f[i][j]/10,f[i][j]%=10;39 while (f[i][cnt[i]+1]) ++cnt[i]; for (RG int j=0;j<=cnt[i];++j) f[i][j]*=i-1;40 for (RG int j=0;j<=cnt[i];++j) f[i][j+1]+=f[i][j]/10,f[i][j]%=10;41 while (f[i][cnt[i]+1]) f[i][cnt[i]+1]+=f[i][cnt[i]]/10,f[i][cnt[i]]%=10,++cnt[i];42 }43 for (RG int i=cnt[n];i>=0;--i) printf("%lld",f[n][i]); return;44 }45 46 int main(){47 File("chess");48 work();49 return 0;50 }
bzoj4563 [Haoi2016]放棋子
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。