题解 Codeforces Round 901 (Div. 1) / CF1874A~E

比赛情况：过了 AB。赛后发现 B 是假复杂度。

A. Jellyfish and Game

Problem

Alice & Bob 又在博弈，Alice 手上有 \(n\) 个苹果，第 \(i\) 个苹果的价值是 \(a_i\)；Bob 手上有 \(m\) 个苹果，第 \(i\) 个苹果的价值是 \(b_i\)。现在开始博弈，双方轮流行动，每次可以将自己的一个苹果和对面的一个苹果交换或者不操作。\(k\) 轮过后，若双方都想最大化苹果价值和并采取最优策略，求 Alice 最终的苹果价值和。\(n,m\leq 50,k\leq 10^9,t\leq 1000\)。

Solution

这个题就是怎么暴力怎么来，首先每一轮的最优策略都是将自己的最小值换成对方的最大值，还有一种策略是还原对面的操作，所以增加的那个量是单调的，会在某一次操作之后变成轮流交换同一对苹果。另外一种解释是说这一对苹果会在 Alice 或者 Bob 第一次操作时拿出来，所以我们只需要模拟前两次操作。暴力决策一下，很快就会循环。

B. Jellyfish and Math

Problem

手上有 \((x, y)\)，每次操作是下列四种之一：

\(x:=x\&y\)
\(x:=x|y\)
\(y:=x\oplus y\)
\(y:=m\oplus y\)

其中这些运算都是位运算，\(m\) 是常数。问能否将 \((x, y)\) 通过操作变换成 \((c, d)\)？\(x, y, c, d\leq 10^9, t\leq 10^5\)。

Solution 1

首先可以按位考虑，完了以后可以发现一个事情就是对于某两位 \(i, j\)，如果 \(x_i=x_j, y_i=y_j, m_i=m_j\)，则做什么操作它们的变化都是一样的，所以我们直接将这些相同的位压缩在一起考虑。现在就只有 \(8\) 位了，更加冷静的分析我们发现某一些种类的位上面做操作能产生的状态数不一定是 4，其实总共也就 \(9000\) 多种状态，直接自信 bfs 可以卡过。

Solution 2

而正解是预处理答案，对于上面说的 \(8\) 种情况，对应的 \(c_i, d_i\) 只有 \(00,01,10,11\) 和询问没有这一位，每一位上一共五种终状，直接预处理答案（使用 bfs），复杂度为 \(O(5^8+T\log V)\)。

C. Jellyfish and EVA

Problem

Alice 和 Bob 共同驾驶名为 EVA 的车执行任务，在一张有向无环图上走（每条边 \((u, v)\) 满足 \(u<v\)，初始时每条边都是黑的），欲将从 \(1\) 移动到 \(n\)。每一次，若 EVA 所在节点为 \(u\)，Alice 和 Bob 按顺序执行以下操作：

若 \(u=n\) 任务成功。
若 \(u\) 没有出边，任务失败。
Alice 按照自己的意志选择一条黑色出边 \(v_1\)。
Bob 随机等概率选择另一条黑色出边 \(v_2\)。
若 \(v_1=v_2\)，EVA 沿着 \(v_1\) 行驶到 \(v_1\) 对应的终点；否则将 \(v_1, v_2\) 染成白色。

问 Alice 绝顶聪明且希望 EVA 到达终点的情况下 EVA 有多大概率任务成功。\(n\leq 2000\)。

Solution

设 \(f_i\) 表示在点 \(i\) 时到达终点的概率。\(f_n=1\) 而我们要求 \(f_1\)。考虑求值 \(f_i\)。

列出 \(i\) 的所有出边 \(v_1, v_2, \cdots, v_k\)。明显，Alice 的策略是每次选择 \(f_v\) 最大的那一个，所以我们对 \(v\) 按照 \(f_v\) 进行排序。如果能得知每个点被一起选的概率 \(p\)，则 \(f_i=\sum_ip_if_{v_i}\)，我们的任务试求 \(p_i\)。

观察到这个 \(p_i\) 非常不好求，除了 \(p_1=\frac 1 k\) 是明晰的，其他点被 Alice 选到时，前面选了什么，影响了后面什么东西，当前是第几次选，变量众多。但是一个观察是选完一次后会删掉两个点，变成规模为 \(k-2\) 的子问题。

不妨对 \(p\) 进行 DP，令 \(h_{k,i}=p_i\)。首先有 \(h_1=\{1\},h_2=\{\frac 1 2, 0\}, h_{i, 1}=\frac 1 i\)。考虑 \(h_{i,j}\)，如果第一次删掉的在 \(j\) 之前，则这种情况的概率是 \(\frac{j-2}{i}\)（不包括自己和第一个），这个 \(h_{i,j}\) 前面删掉两个，变成 \(h_{i-2, j-2}\)。如果第一次删掉的在 \(j\) 之后，则这种情况的概率是 \(\frac{i-j}{i}\)，前面删掉一个变成 \(h_{i-2,j-1}\)。于是可以进行 DP。概率之和不为一是因为有失败的。

\(O(n^2)\)。

D. Jellyfish and Miku

Problem

JellyFish（天啊终于只有它她一个人了）在一条数轴上，数轴上只有 \(0, 1, 2, \cdots, n\) 这些点，JellyFish 在 \(0\) 想走到 \(n\)，但是 JellyFish 的移动方式很特别，她需要一个数组 \(\{a_i|1\leq i\leq n\}\) 指导行动，在 \(i\) 点时有 \(\frac{a_i}{a_i+a_{i+1}}\) 的概率向左走 -1，有 \(\frac{a_{i+1}}{a_i+a_{i+1}}\) 的概率向右走 \(+1\)（定义 \(a_0=0\)）。因为 JellyFish 的名字有九个字符，所以你需要给她造一个数组 \(a_i\geq 1\) 还要满足 \(\sum_i a_i\leq m\) 以使得 JellyFish 第一次到达 \(n\) 的期望步数最小。\(n\leq m\leq 2000\)。

E. Jellyfish and Hack

Problem

fun :: Ord a => [a] -> Int
fun [] = 0
fun (x:xs) = smaller + larger + len
    where smaller = fun [a | a <- xs, a <= x]
          larger  = fun [a | a <- xs, a > x]
          len = length xs + 1

求有多少个 \(n\) 阶排列 \(p\) 使得 \(fun(p)\geq lim\)。\(n\leq 200, lim\leq 10^9\)。注意，模数是 \(10^9+7\)，时限 8s。

Solution

观察到 \(lim\leq 10^9\) 是诈骗，实际上只需要 \(lim\leq n(n-1)/2\)（每次都是全部递归）。

然后我们有一些比较显然的 DP：设 \([x^j]f_i\) 表示 \(i\) 阶排列使得 \(fun(p)=j\) 的答案（多项式）。那么明显有：

\(f_0=0\)。
\(f_i=x^i\sum_{j=1}^i\binom{i-1}{j-1}f_{j-1}f_{i-j}\)。（枚举第一项是什么，然后选出左右两边，选完之后比它大的那一部分整体间隔什么东西，不影响答案）

那么直接做就是 \(O(n^2)\) 次多项式乘法，每次是两个 \(O(n^2)\) 的多项式相乘。这时我们拍出 FFT，一看，模数不对！

我们换个思路，因为 FFT 本质是一种插值，我们将 FFT 改成拉格朗日插值即可。每次做乘法实际上不是做乘法，而是将点值对应相乘。然后再将 \(f_n\) 换回去，得到各项系数之后怎么搞都行。总的复杂度是 \(O(n^4)\)，注意实现要好一点别多 \(\log\) 了。然后点值甚至可以随便选。拉格朗日插值的时候可以先求出来 \(\prod(x-x_i)\)，然后每次再除掉 \((x-x_i)\) 乘上一些逆元，乘除都直接暴力，这样求出各项系数，复杂度是正确的。