[AGC001E] BBQ Hard 题解
计数题好题。
思路
考虑 \(\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记录。