首页 > 代码库 > BZOJ4563 [Haoi2016]放棋子

BZOJ4563 [Haoi2016]放棋子

2024-08-13 09:24:57   211人阅读

Description

给你一个N*N的矩阵，每行有一个障碍，数据保证任意两个障碍不在同一行，任意两个障碍不在同一列，要求你在
这个矩阵上放N枚棋子（障碍的位置不能放棋子），要求你放N个棋子也满足每行只有一枚棋子，每列只有一枚棋子
的限制，求有多少种方案。

Input

第一行一个N，接下来一个N*N的矩阵。N<=200,0表示没有障碍，1表示有障碍，输入格式参考样例

Output

一个整数，即合法的方案数。

Sample Input

2
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]放棋子


联系
我们