【CF960G】Bandit Blues

Source and Judge

CF960G

Record

3h

Analysis

请先思考后再展开

考虑一些性质,发现最高点一定是n,然后左边关键点上升右边下降
考虑n个位置,有k个是特殊点的方案数,考虑从大到小放入,考虑最小值的位置可得递推式
$dp(n,k)=dp(n-1,k-1)+(n-1)dp(n-1,k)$
发现这就是第一类斯特林数
那么答案就是 $\sum_{i=1}^n {n-1 \choose i-1} S(i-1,a-1) S(n-i,b)$
发现这样太慢了,主要原因是两个方向,考虑优化这个东西
只从一个方向看,然后把b-1个翻转过去即可
${a+b-2 \choose a-1} S(n-1,a+b-2)$
一个log求斯特林数详见这里

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/62ca.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%