CF717 题解

[toc]

AC 代码

A. Tit for Tat

贪心，按 $a_0,a_1,\ldots,a_{n-2}$ 这个顺序进行减一操作，加一操作永远对 $a_{n-1}$ 实行。

B. AGAGA XOOORRR

给定一个大小为 $n$ 的数列 $a$ ，每次可以将两个相邻的整数 $a_i,a_{i+1}$ 替换为 $a_i\oplus a_{i+1}$ ，询问最后能否恰好剩下至少两个相等的整数。

$2\leq n\leq 2000$ 。

由于只能替换相邻的整数，因此最后留下的数字一定是由一系列连续子串异或和构成的。然后再思考一下题目中至少两个这一条件，容易发现，如果数列 $a$ 的异或和为 $0$ ，那么必定有解；否则数列至少需要被分成三段。于是，异或和不为零时，我们只需要求出数列的异或前缀和，查询是否有至少三段前缀和等于数列的异或和。

C. Baby Ehab Partitions Again

给定一个大小为 $n$ 的数列 $a$ ，询问你最少需要删除数列中的几个数才能使得以下条件成立：

你无法将数列 $a$ 分成两个子序列，这两个子序列的和相等。

并给出删除的是哪些数。

$2\leq n\leq 100,1\leq a_i\leq 2000$ 。

首先，不难发现本题至多删除一个数即可，下面进行一个简单的说明：

我们可以通过背包先预处理是否需要删除，如果需要删除就说明数列之和是一个偶数，此时如果数列中存在奇数，那么奇数一定成对出现，只需要删除其中一个即可。如果数列中全是偶数怎么办呢？实际上，如果数列全是偶数，那么数列整体除以 $2$ 即可，持续这一操作直到出现一个奇数为止。

~~以上都是看了官方题解之后写的，真正做的时候用随机 + 记忆化 + dp 暴力查找冲过去了。~~

D. Cut

给定一个大小为 $n$ 的数列 $a$ 和 $q$ 次询问，每次询问一段区间 $[l,r]$ ，问至少要把这个区间分为几个子区间，才能使得每个子区间内的数的乘积等于这个子区间内所有数的 $\text {lcm}$ 。

$n,a_i,q\leq 10^5$ 。

对于每个 $i$ 预处理出它最远向右能够到达的位置 $nxt [i]$ ，这个 $nxt$ 数组一定是单调不减的，因此可以双指针 $O (n)$ 扫过去，每一次检查新加入的数字 $a_j$ 是否与 $a_i,a_{i+1},\ldots,a_{j-1}$ 有公因子。

然后就是本题的关键：对于任意一段区间 $[l,r]$ ，最优解一定是这样一系列子区间： $[l,nxt [l]],[nxt [l]+1,nxt [nxt [l]+1]],\ldots$ 。因此我们要做的就是从 $l$ 开始向右跳跃： $l\rightarrow nxt [l]+1\rightarrow nxt [nxt [l]+1]+1\rightarrow\cdots$ ，直到当前的下标大于等于 $r$ 就停止跳跃，答案即为向右跳跃的次数。

由于我们已经预处理出了 $nxt$ 数组，因此整个数组已经可以建成一个树的形态，向右跳跃的操作可以在树上倍增地跳，直到 $l$ 的深度跳到和 $r$ 相同为止，此外还需要注意一个特殊情况： $l$ 和 $r$ 虽然深度一样，但是 $a_r>a_l$ ，此时我们还需要再向上跳一步。

E. Baby Ehab Plays with Permutations

给定一个初始为 $1,2,3,\cdots,n$ 的排列，你可以进行 $j$ 次操作，每次操作可以交换排列中任意两个数，询问 $j$ 次操作后有几种不同的排列。求出 $j=1,2,3,\cdots,k$ 的所有结果。

$2\leq n\leq 10^9,k\leq 200$ 。

初始状态下，一个 $1$ 到 $n$ 的排列中的所有元素都可以看作是 $n$ 个大小为 $1$ 的圆排列（实际上就是 $n$ 个指向自己的环）。

然后考虑交换 $1$ 次对于这些圆排列的影响，比如 $[1,2,3,4]$ 交换 $1$ 次后可能得到 $[2,1,3,4]$ ，这个时候新的排列实际上由 $3$ 个圆排列（环）构成： $[2,1],[3],[4]$ ，其他情况同理。这意味着，交换 $1$ 次后， $n$ 个圆排列只剩下 $n-1$ 个。然后，我们考虑交换 $2$ 次，经过测试不难发现交换 $2$ 次后圆排列要么有 $n-2$ 个，要么有 $n$ 个，这提示我们每一次的交换，我们都可以让圆排列的数量减少 $1$ （最少为 $1$ ）或者撤销前一次的交换。

因此如果我们设大小为 $n$ 的排列构成 $k$ 个圆排列的方案数为 $s (n,k)$ ，那么本题的答案就是： $s (n,n-1),s (n,n)+s (n,n-2),s (n,n-1)+s (n,n-3),\cdots$ 。

这里的 $s (n,k)$ 实际上就是第一类斯特林数的定义，我们直接求值就可以解决了。。。等等 $n\leq10^9,k\leq 10^2$ ，但我只会 $O (n^2)$ 递推啊！不要慌，打开无敌的 wiki，在 Stirling Numbers of the First Kind 中我们发现了这个式子：

\begin{aligned} s(n,n-i) = \sum^i_{j=0}(-1)^j\binom{n-1+j}{i+j} \binom{n+i}{i-j}S(i+j, j) \end{aligned}

上式中 $S (i+j,j)$ 表示第二类斯特林数，因此我们只需要预处理一下第二类斯特林数，就可以在 $O (k^3)$ 的复杂度下解决本题了。