一个很妙的优化。
我们考虑 (x+yx) 的组合意义,是从 (0,0) 到 (x,y) 的方案数量。于是考虑这个式子本质上就是求 (0,0) 到 (ai+aj,bi+bj) 的路径数量。
这个东西看起来也不太能做。但是发现我们可以给它变成求 (−ai,−bi) 到 (aj,bj) 的方案数量。这个东西就可以 dp 了,设 dp[x][y] 表示 所有点到 (x,y) 的方案数量。初始给 (−ai,−bi) 设为 1 即可。
最后需要减去重复酸的,也就是自己到自己的方案数量。
cpp
1 |
|