526互联

[AGC001E] BBQ Hard 题解

发布时间 2023-08-18 09:51:16作者: Al_lA

计数题好题。

思路

考虑 \(\dbinom{n+k}{k}\) 的几何意义。

即从 \((1,1)\) 到 \((k,n)\) 只往上或往右走的方案数。

由于这个在几何上坐标可以平移。

也就是 \((1-x,1-y)\) 到 \((k-x,n-y)\) 的方案与 \((1,1)\) 到 \((k,n)\) 的方案数是一样的。

那么我们就可以求出所有 \((1-a_i,1-a_j)\) 到 \((i,j)\) 的方案。

最后直接 \(dp\) 即可。

Code

AC记录。