20241022 模拟赛
A. 枚举高手
考虑 dp，设 \(f_{i,j}\) 表示考虑到第 \(i\) 个数，和为 \(j\) 的答案，\(g_{i,j}\) 表示方案数。考虑两种转移：一种是在原序列的末尾加上一个 \(1\)，一种是把现有的数一起加上 \(1\)，容易发现这样既能保证有序性又能不重不漏。时间复杂度 \(O(nm)\)。
最近总是 MLE，要注意了！！！
B. 砸地鼠
考虑一个不带修改，也就是砸完地鼠不会消失的版本，设区间内有 \(a\) 个 \(1\)，\(b\) 个 \(2\)，那么答案即为：
\[\cfrac{2^xc+2^{x-b}\sum\limits_{i=0}^biC_b^i}{r-l+1} \]注意到 \(2^{x-b}\sum\limits_{i=0}^biC_b^i=2^{x-b}\times(\cfrac b2\times2^b)=2^x\times\cfrac b2\)。
标签：limits,sum,biC,cfrac,b2,模拟,20241022 From： https://www.cnblogs.com/luyuyang/p/18535177