B 的 dp 做法。 本文同步发表于个人博客:Link。 题意 在左下角是 (0,0)(0,0)(0,0),右上角是 (W,H)(W,H)(W,H) 的网格上,有 (W+1)×(H+1)(W+1)\times (H+1)(W+1)×(H+1) 个格点。 现在要在格点上找 NNN 个不同的点,使得这些点在一条直线上。并且在这条直线上,相邻点之间的距离不小于 DDD。求方案数模 109+710^9+7109+7。 解析 纯组合方法求方案数,是我不会的东西。所以赛时就考虑用 dp 来统计方案数。 通过 P3166 [CQOI2014]数三角形 的套路,我们可以想到枚举 (x,y)(x,y)(x,y)...