我是靠谱客的博主 外向蜻蜓,这篇文章主要介绍hdu 5794 A Simple Chess (dp+lucas定理),现在分享给大家,希望可以做个参考。

2016 Multi-University Training Contest 7  1002

hdu5794  A Simple Chess


题意:有一个棋盘,上面有一个棋子,棋子走法和象棋中的马一样,且只能向右下方走。棋子一开始在左上角(1,1)要使求棋子走到右下角(n,m)。棋盘上有r个障碍点不能通过(不考虑蹩马腿),问棋子走到右下角的方法数取模后答案。


在赛场上想的是lucas定理+容斥,看了看数据感觉过不了没敢写,赛后知道果然还是煞笔数据,把不可达点去掉后完全可以O(2^n)容斥(官方题解说的)。

补题的时候参考的别人的dp写法。


最后

以上就是外向蜻蜓最近收集整理的关于hdu 5794 A Simple Chess (dp+lucas定理)的全部内容,更多相关hdu内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(40)

评论列表共有 0 条评论

立即
投稿
返回
顶部