111qqz的小窝

老年咸鱼冲锋!

codeforces 560 E. Gerald and Giant Chess (dp+lucas定理,求大组合数 mod p,p为质数)

dp方程想错了.果然还是欠练啊.

如果我们不考虑坏点,那么从 (0,0)到(x,y)的方案数是c(x+y,x)或者c(x+y,y)

因为有坏点的存在,我们可以逆向思维,先求出总数,然后减去那些由于坏点的影响不能走的方案数.

由于存在黑点i(x,y),从左上到该黑点的方案数sum[i] = C(x+y,x),其中如果在黑点i的左上还有黑点j(u,v),那么应该减去sum[j]*C(x-u+y-v)(y-u)

然后可以把坏点按照x为第一关键字,y为第二关键字排序.

从左上出发,往右下扫黑点.

还有一个考点是大组合数的求法

因为太大,递推也不行.

可以用欧拉公式求逆元的方法求解.

或者是lucas定理.

记得拿到骑士(1,1)到(n,m)的题和这道题很像.

也是从坐上到右下,中间有些坏点,不过骑士的走法并不是向下或者想有1步,而是向右p步,向下q步,或者向又q步,向下p步.

而且那道题的n和m是 10^9的数量级…

那道题的话就只能用lucas定理了貌似

这道题算是那道题的弱化版本,在此orz zhangk,果然厉害

所以我还是决定写lucas定理的解法

lucas定理适用于 求C(n,m)%p,p为素数 且n,m很大的情况.

引用一段题解:

说点什么

您将是第一位评论人!

提醒
wpDiscuz
粤ICP备18103363