【HAOI2016】放棋子

2018-03-18 22:16:20


偶然翻到这道题,突然发现我以前写的题解质量看上去居然还不错
讲东西应该是我的强项把hhh(当然要再自己理解的情况下
好想讲课啊(x
那就直接把以前写的转载过来:
新博客链接
旧博客链接

棋盘放置,这个跟组合数学有点关系(应该没有),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

然后这道题就完结了,出题人为了不让推出递推式的同学瞬间秒掉这道题,增加代码复杂度,答案没有膜数,需要高精度

然而可以发现递推式中只有高精加高精和高精乘单精,也不怎么难写(就算是这样,高精度还是有不少细节需要注意

我是偶然发现了两个特殊性才想出这道题,虽然这次依旧没有想起来去往题目特殊性的方面去思考,但是再次证明了想题主要思考特殊性而不是一般性

总之这道题就是发现特殊性(不是太难看出来),往递推的方面思考(思路不要歪到组合数上去),高精度别写挂(注意对拍)就可以拿到满分辣