首页 > 代码库 > 【HAOI2016】放旗子
【HAOI2016】放旗子
终于自己推出来一道题了quq然而时间有点久，考场上并不大丈夫……
原题：
给你一个N*N的矩阵，每行有一个障碍，数据保证任意两个障碍不在同一行，任意两个障碍不在同一列，要求你在这个矩阵上放N枚棋子（障碍的位置不能放棋子），要求你放N个棋子也满足每行只有一枚棋子，每列只有一枚棋子的限制，求有多少种方案。
N<=200
棋盘放置，这个跟组合数学有点关系（应该没有），N<=200，看上去可以DP（应该不能）
然后我在想组合数学和DP的时候首先发现了两点特殊性：
棋盘的每一行是可以随便换的，因为每行每列互不干扰（产生限制的是棋子），所以可以把所有n相等的情况都看做一种，也就是说题目中给出的棋盘并没有什么卵用（其实如果写20的dfs或60的壮鸭还是要用的
为了方便研究，现在约定每个棋盘上被限制的位置都是从坐上到右下，比如n==4的时候就是酱紫：
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
然后如果安行选的话，第i行第j列选完之后，就可以看做把第i行和第j列删掉了
比如上面的n==4的情况，如果删掉第1行第2列，这个方阵就会变成下面酱紫：
0 0 0
0 1 0
0 0 1
多手玩几组数据后容易发现，上面删除后的矩阵有非常亦可赛艇的特点
这是一个3*3的棋盘，并且从(2,2)到(3,3)和2*2的棋盘是一样的（在开始的时候就约定了把所有n相等的情况都看做一种
所以这也可以看成3*3的左上角变成0
接下来在第一行放棋子有两种选择，要么不在(1,1)放，方案数等于3*3的，在(1,1)放，就可以把第一行和第一列删掉，剩下的棋盘就是个2*2的，也就是说在(1,1)放的方案数等于2*2的
所以上面这个被删过的矩阵的方案数就是2*2的方案数+3*3的方案数
因为这个被拿来举例的矩阵是删掉(1,2)的结果，同样也可以删掉(1,2~n)，共有n-1种删法，易证每种删法都符合上面的性质
这样就得到了一个关于n*n棋盘方案数的正确表示，可以发现n*n棋盘的方案数只与(n-1)*(n-1)的方案数和(n-2)*(n-2)的方案数有关，这些都是在n之前的量（这话有点奇怪，可以忽略
所以就可以列出递推式，用f[i]表示i*i棋盘的方案数，f[i]=(f[i-1]+f[i-2])*(i-1)，初始状态为f[1]=0，f[2]=1
然后这道题就完结了，出题人为了不让推出递推式的同学瞬间秒掉这道题，增加代码复杂度，答案没有膜数，需要高精度
然而可以发现递推式中只有高精加高精和高精乘单精，也不怎么难写（就算是这样，高精度还是有不少细节需要注意
我是偶然发现了两个特殊性才想出这道题，虽然这次依旧没有想起来去往题目特殊性的方面去思考，但是再次证明了想题主要思考特殊性而不是一般性
总之这道题就是发现特殊性（不是太难看出来），往递推的方面思考（思路不要歪到组合数上去），高精度别写挂（注意对拍）就可以拿到满分辣
（然而在考场上我还是想不出来quq
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 const int dalao=10000; 8 void splay(int &x){int mk=1; char ch=getchar(); 9 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)mk=-1; ch=getchar();} 10 while(ch>=‘0‘&&ch<=‘9‘){x=(x<<3)+(x<<1)+ch-‘0‘; ch=getchar();} 11 x=0; 12 } 13 int n; 14 int f[210][510],l[210]; 15 int a[210]; 16 int main(){//freopen("ddd.in","r",stdin); 17 cin>>n; 18 int root; 19 //for(int i=1;i<=n;++i)for(int j=1;j<=n;++j) splay(root); 20 f[2][1]=1,l[1]=l[2]=1; 21 for(int i=3;i<=n;++i){ 22 /*l[i]=l[i-1]+l[i-2]-1; 23 for(int j=1;j<=l[i-1];++j) 24 for(int k=1;k<=l[i-2];++k){ 25 f[i][j+k-1]+=f[i-1][j]*f[i-2][k]; 26 f[i][j+k]+=f[i][j+k-1]/dalao,f[i][j+k-1]%=dalao; 27 }*/ 28 l[i]=max(l[i-1],l[i-2]); 29 for(int j=1;j<=l[i];++j){ 30 f[i][j]+=f[i-1][j]+f[i-2][j]; 31 f[i][j+1]+=f[i][j]/dalao,f[i][j]%=dalao; 32 } 33 while(f[i][l[i]+1]) ++l[i],f[i][l[i]+1]+=f[i][l[i]]/dalao,f[i][l[i]]%=dalao; 34 for(int j=1;j<=l[i];++j) a[j]=f[i][j],f[i][j]=0; 35 for(int j=1;j<=l[i];++j){ 36 f[i][j]+=a[j]*(i-1); 37 f[i][j+1]+=f[i][j]/dalao,f[i][j]%=dalao; 38 } 39 while(f[i][l[i]+1]) ++l[i],f[i][l[i]+1]+=f[i][l[i]]/dalao,f[i][l[i]]%=dalao; 40 } 41 cout<<f[n][l[n]]; 42 for(int i=l[n]-1;i>=1;--i) printf("%04d",f[n][i]); 43 cout<<endl; 44 return 0; 45 }
【HAOI2016】放旗子