题解：P13037 [GCJ 2021 #2] Hidden Pancakes

Expert_Dream · 2026-08-07 20:53:29 · 题解

考虑 [1,n] 区间最后一个 1 必定最大值，记在位置 p，那么 [1,p) 与 (p,n] 其实是互不相干的，所以考虑可以去分治，往 [1,p-1] 和 [p+1,n] 去递归，对左边找 1，对右边找 2，推广到全局一样的。答案统计就是 \operatorname{sol}(l,r) = \operatorname{sol}(l,p-1) \times \operatorname{sol}(p+1,r) \times \dbinom{r-l}{p-l}。找 p 可以直接二分。