首页 > 代码库 > 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[n]为n的错排方案数，则f[n]=(f[n-1]+f[n-2])*(n-1)表示错排方案数的递推公式。要解释的话也很好解释，错排可以理解为n个点和n个点排成两行互相连边，不能有相同位置的点相连。那么n可以在n-1的基础上进行，可以视为新添加两个点，如果前n-1个已经满足错排的条件，那么这两个与其中任意一个互相交叉互换也一定满足；如果前n-1个有1个不满足，那么就找出那个不满足的，与新加入的两个点直接交叉即可。
得到递推公式之后，就可以直接推了。数字显然很大，就写个高精度就可以了。
1 //It is made by jump~ 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <algorithm> 8 using namespace std; 9 typedef long long LL;10 const int MAXN = 201; 11 const int MOD = 100000000;12 int n;13 LL f[MAXN][50];14 int cnt[MAXN];15 //f[n]=(f[n-1]+f[n-2])*(n-1)表示错排方案数的递推公式，因为可以视为新添加两个点，如果前n-1个满足，那么这两个与其中任意一个互相交叉互换也一定满足；如果前n-2个满足，最后两个不满足，那么直接交叉也使得可以满足。16 17 int main()18 {19 scanf("%d",&n); f[1][0]=0; f[2][0]=1; 20 for(int i=3;i<=n;i++) {21 for(int j=0;j<=cnt[i-1];j++) f[i][j]=f[i-1][j]+f[i-2][j];22 cnt[i]=cnt[i-1]; for(int j=0;j<=cnt[i-1];j++) f[i][j+1]+=f[i][j]/MOD,f[i][j]%=MOD;23 while(f[i][cnt[i]+1]) cnt[i]++;24 for(int j=0;j<=cnt[i];j++) f[i][j]*=(i-1);25 for(int j=0;j<=cnt[i];j++) f[i][j+1]+=f[i][j]/MOD,f[i][j]%=MOD;26 while(f[i][cnt[i]+1]) cnt[i]++;27 }28 printf("%lld",f[n][cnt[n]]);29 for(int i=cnt[n]-1;i>=0;i--) printf("%08lld",f[n][i]);30 return 0;31 }
BZOJ4563 [Haoi2016]放棋子
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。