[HAOI2017]方案数[组合计数、容斥、dp]

论坛 › 期权论坛 › 编程之家

 选择匿名的用户  2021-6-2 16:23  1789  0

题意

分析

先考虑没有障碍怎么做，定义 f(i,j,k) 每一维走了 i,j,k 位的方案数，转移乘个组合数即可。
现在多了一些障碍，考虑容斥。实际我们走过的点都有严格的大小关系，所以先把所有障碍点按维度排序，然后定义 g(i,j) 表示走到 i 这个障碍点，走了 j 个障碍点的方案数，利用 f 转移。实际第二维在转移时乘以-1就可以忽略。
复杂度 \(O(o^2)\)
开始写的刷表发现有问题，因为刷表时的所有状态都和 (n,m,r) 有关，所以中间的状态不能表示和终态一样的意义。

代码

转载于:https://www.cnblogs.com/yqgAKIOI/p/10410303.html

回复

分享到 :

0 人收藏

16级独孤

选择匿名的用户

积分:3875789

帖子:775174

精华:0

+ 关注私信

期权论坛

期权论坛

期权网络科技版权所有: 关于我们; 联系我们; 加入我们; 反馈问题; 免责声明; 积分充值

统一社会信用代码: 积分规则; 网站地图; 爱文库; 下属网站

官方: 新浪微博; 微信公众号
◆

下载: 表情包; App下载

期权论坛

期权论坛

QQ咨询|关于我们|Archiver|手机版|小黑屋|( 辽ICP备15012455号-4 ) Powered by 期权论坛 X3.2 © 2001-2016 期权工具网&期权论坛 Inc.