【CF960G】Bandit Blue【FJOI2016】建筑师

Source and Judge

CF960G

loj2173

Analysis

请先思考后再展开

新写的题解

FJOI2016出原题是什么鬼……还削弱了,不知道是好是坏

只考虑a+b-1个关键点的话显然是个山

如果枚举n的位置:$ans=\sum_{i=1}^n C_{n-1}^{i-1}S_1(i-1,a-1)S_1(n-i,b)$

考虑怎么避免枚举n的位置,考虑上面式子的组合意义,你发现完全可以写成:

${a+b-2 \choose a-1} S_1(n-1,a+b-2)$,那么求斯特林数就好啦

FJOI2016直接用递推式就好了,CF的话快速求法见这里,之前雅礼集训出这道题要nlogn才能过


老题解

考虑一些性质,发现最高点一定是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
转载请注明出处,谢谢!