网站首页
编程语言
数据库
系统相关
其他分享
编程问答
格路
2024-12-14
容斥技巧(长期更新)
普通容斥反射容斥用于格路计数问题,可以在转移与格路计数类似的DP中见到,然后直接用数学方法优化。首先容易得到\((x_0,y_0)\)关于\(y=x+b\)对称得到\((y_0-b,x_0+b)\)。以及\((0,0)\)走到\((n,m)\)的方案数为\(\binom{n+m}n\)。先来考虑一下Catalan数的格路计数的推导方式解