当前位置：首页 > news >正文

【A】月半猫想吃麦当劳（待完坑）

news 2025/9/17 3:31:41

CF660E

考虑从子序列从第一次出现的地方去贡献每个数列。
如果我们有一个子序列为 $a_{p_1},a_{p_2},a_{p_3},\cdots,a_{p_i}$，那我们要求：$a_{p_i}$ 在 $a_{p_{i-1}+1\sim p_i}$ 中第一次出现。
容易列出式子：$\sum_{i=1}^n m^i \sum_{j=i}^n \binom{j-1}{i-1}(m-1)^{j-i}m^{n-j}$。其中 $i$ 枚举的是子序列的长度，$j$ 枚举的是 $p_i$。
化简：$$\begin{aligned} &\sum_{i=1}^n m^i \sum_{j=i}^n \binom{j-1}{i-1}(m-1)^{j-i}m\ =& \sum_{j=1}^n\sum_{i=1}j \binom{j-1}{i-1}(m-1)^{j-i}m\ =&\sum_{j=1}^n\sum_{i=1}j \binom{j-1}{i-1}(m-1)^{{(j-1)-(i-1)}m}\ =&\sum_{j=1}^n m^{{n-(j-1)}\sum_{i=0}} \binom{j-1}{i}(m-1)^{(j-1)-i}m\ =&\sum_{j=1}^n m^{{n-(j-1)}(2m-1)}\ =&\sum_{j=0}^{n-1} m^{n-j}(2m-1)\ \end{aligned}$$
注意空子序列要单独计算，贡献为 $m^n$。

CF1930E

令最终 $a_i$ 被删去记作 $0$，否则记作 $1$。
01 序列合法的充要条件为：

$0$ 的数列为 $2k$ 的倍数。

存在 $1$ 满足左右都至少存在 $k$ 个 $0$。

证明：考虑回撤最后一次操作。首先在这个 $1$ 左右两边各选 $k-1$ 个 $0$ 变成 $1$。如果左边的 $0$ 多，那任意标记一个右边的 $0$，然后标记处于中间位置的 $0$ 为 $1$（显然在左边）。否则反之。发现子问题满足上述约束，递归证明命题。
枚举 $k$ 和操作次数 $c$，用所有方案 $\binom{n}{2ck}$ 减去不合法的方案。
不合法的方案满足：左边第 $k$ 个 $0$ 到右边第 $k$ 个 $0$ 之间都是 $0$。把这 $x=2ck-2k+2$ 个 $0$ 缩起来，相当于在 $n-x+1$ 个位置中选出 $2k-1$ 个 $0$。

CF1784D

从根往下考虑，设 $f_{i,u}$ 表示 $u$ 是子树内第 $i$ 层的胜者，且考虑了除了 $u$ 的对手子树外的排列方案数。
$f_{0,u}=[u=0],f_{i,u}=2\times(2^{n-i})!\binom{2^n-2^{n-i}-u}{2^{n-i}-1}\sum_{j=1}^{u-1}f_{i-1,j}$

其中 $f_{0,u}=[u=0]$ 表示一开始是一个虚拟的胜者，并不知道其具体是什么。系数的意义：$2$ 表示蓝色、黑色两棵子树不关心顺序；$(2^{n-i})!$ 表示确定黑色子树内的数的顺序；$\binom{2^n-2^{n-i}-u}{2^{n-i}-1}$ 表示黑色子树内最小值已经被我们后面那个枚举确定，然后其他的 $2^{n-i}-1$ 个数需要我们从 $(j,2^n]$ 中确定。
最终 $u$ 的答案为 $\sum_{j=1}^{u-1}f_{n,j}$，时间复杂度 $O(2^nn)$。

CF1976E

补

CF1558D

考虑我们最终的序列为 $a_{p_1},a_{p_2},\cdots,a_{p_n}$。我们有一些限制：$a_{p_i}\le a_{p_{i+1}}$ 或 $a_{p_i}<a_{p_{i+1}}$。
如果我们有 $x$ 个小于号，$n-1-x$ 个小于等于号，方案数为：$\binom{2n-1-x}{n}$。
考虑模拟计算 $x$，可以使用平衡树或者线段树。复杂度 $O(m\log n)$。
具体维护方法：倒序枚举这些插入 $(x_i,y_i)$，那么对于当前的第 $y_i$ 个数 $p$ 和 $y_i+1$ 个数 $q$，表示 $p$ 插入到 $q$ 前面了，于是我们把 $p$ 删除，给 $q$ 打上 $tag$，表示 $q$ 前面的小于号。最后数 $tag$ 个数即可。

CF1781F

使用经典转化，( 看作 1，) 看作 -1，合法：前缀和全部都是非负。
第 $i$ 次插入到某个位置的概率为 $\frac{1}{2i-1}$，可以最后乘。
发现插入 () 等于把前缀和数组中 $x\rightarrow x,x+1,x$，)( 等于把前缀和数组中 $x\rightarrow x,x-1,x$。
设 $f_{i,x}$ 表示一开始前缀和为 $x$，没有任何括号，然后插入 $i$ 次后合法的方案数。
$f_{n,x}=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}p\binom{n-1}{i}\binom{n-i-1}{j}f_{i,x}f_{j,x+1}f_{n-i-j-1,x}+\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}(1-p)\binom{n-1}{i}\binom{n-i-1}{j}f_{i,x}f_{j,x-1}f_{n-i-j-1,x}$
转移式是三个东西卷积，复杂度 $O(n^4)$。考虑先预处理其中两个卷积，然后再与第三个卷就好了。复杂度 $O(n^3)$。

CF1716F

有人机式子：$\sum_{i=0}^{n}i^k\binom{n}{i}x^iy^{n-i}$，其中 $x=\left\lceil\frac{m}{2}\right\rceil,y=\left\lfloor\frac{m}{2}\right\rfloor$。
考虑使用第二类斯特林数。$$\begin{aligned} &\sum_{i=0}^n\sum_{j=0}kS_2(k,j)i^{\underline j}\binom{n}{i}x^iy\ =&\sum_{i=0}^n\sum_{j=0}kS_2(k,j)n^{\underline j}\binom{n-j}{i-j}x^iy\ =&\sum_{j=0}^kS_2(k,j)nx^j\sum_{t=0}\binom{n-j}{t}x^{t}y\ =&\sum_{j=0}^kS_2(k,j)nx^jm\ \end{aligned}$$

CF1924D

不妨令 $n>m$。先考虑经典问题：有 $k$ 对括号，合法的括号序列方案数为 $\binom{2k}{k}-\binom{2k}{k-1}$。
仍然考虑走路。从 $(0,0)$ 走到 $(n+m,n-m)$。考虑如何求最大合法括号子序列？记录一个 $tot$ 表示左括号数列，如果遇到右括号就 tot--,ans++，前提是 tot>0。
考虑模拟这个走路的过程。在原本的图像上，每次突破最小值就会导致这个括号不被计算，于是我们要求最低点为 $k-m$ 的折线个数。
对于 $k>m$ 无解。考虑差分，设 $f_t$ 表示最低点小于等于 $t$ 的方案数。那我们求 $f_{k-m}-f_{k-m-1}$。
对于 $f_t$，我们考虑将触及 $t$ 的线段从第一个交点处翻转，那我们求 $(0,0)\rightarrow (n+m,2t-(n-m))$，即 $f_t=\binom{n+m}{n-t}$。