【HAOI2016】放棋子

偶然翻到这道题，突然发现我以前写的题解质量看上去居然还不错 讲东西应该是我的强项把hhh（当然要再自己理解的情况下 好想讲课啊（x 那就直接把以前写的转载过来： [新博客链接](https://cdcq.blog.luogu.org/solution-p3182) [旧博客链接](http://www.cnblogs.com/JSL2018/p/6431930.html) 棋盘放置，这个跟组合数学有点关系（应该没有），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 然后这道题就完结了，出题人为了不让推出递推式的同学瞬间秒掉这道题，增加代码复杂度，答案没有膜数，需要高精度 然而可以发现递推式中只有高精加高精和高精乘单精，也不怎么难写（就算是这样，高精度还是有不少细节需要注意 我是偶然发现了两个特殊性才想出这道题，虽然这次依旧没有想起来去往题目特殊性的方面去思考，但是再次证明了想题主要思考特殊性而不是一般性 总之这道题就是发现特殊性（不是太难看出来），往递推的方面思考（思路不要歪到组合数上去），高精度别写挂（注意对拍）就可以拿到满分辣