【AGC001E】BBQ Hard

好神啊

可以发现两根之间的答案为\(\binom{a_i+a_j+b_i+b_j}{a_i+a_j}\)

看到这个组合数可以想到是某个点只能往右或上走到某个点的方案数

可以把\(i,j\)的贡献看成是\((-a_i,-b_i)\)走到\((a_j,b_j)\)的方案数

由于\(a,b\)的值域比较小,可以在平面上对每根竹签暴力建\((-a_i,-b_i)\)和\((a_i,b_i)\)两个点。新建源汇点,从源点向每个第三象限的点连边,从每个第一象限的点向汇点连边,答案就是源点走到汇点的方案数。在平面上dp,最后减掉算多的即可。

说点什么

您将是第一位评论人!

提醒
wpDiscuz