CF改题

有长为 $n$ 的正整数序列 $a_i$ ，和一个集合 $S=\{p_1,p_2,\dots,p_m\},1\le p_1<p_2<\dots<p_m\le n$ ，求 $\sum\limits_{\empty\not=T\sub S}\sum\limits_{i=1}^na_i\min\limits_{j\in T}|i-j|$

求期望有个式子 $E(X)=\sum_x f(X\ge x)$ ，概率论里面学的。

考虑变一下 $\sum\limits_{\empty\not=T\sub S}\min\limits_{j\in T}|i-j|=\sum\limits_k\text{点全在}[i-k,i+k] \text{外面的情况}$ ，记 $f_i$ 表示 $[1,i]$ 中 $p$ 的个数

上式即为 $\sum_k (2^{m-(f_{i+k}-f_{i-k-1})}-1)$ ，枚举一下 $f$ 的两个下标 $\sum\limits_{j<k,j+k=2\times i-1}2^m\frac{2^{f_k}}{2^{f_j}}-1$

是一个卷积的形式，对于 $j<k$ 这个限定的偏序需要使用一下 CDQ 分治，另外这个题还得注意一下枚举的下标是有负数的。

给 $m$ 个长度均为偶数的正整数数组，要求令每个数组分一半数到 $1$ 集合，分另一半数到 $2$ 集合，最后问能不能让这两个集合完全相同并构造方案。

研究一下发现如果值出现次数都是偶数貌似都行，然后开始大力构造。

强行构造好像讨论一下 case 也可以做但是很麻烦，这里介绍介绍官方给的图论做法（图论做法好像不少，不过官方这个可能更加容易想吧）

首先观察为什么可以放到图论模型上，这里有一个二则，每个数要么去 1 要么去 2；和两个约束，每个数组去两边的元素个数相同，每个值去两边的元素个数也要相同。

一个二则在图论模型中有时候会被认为是给有向边定向，这启发我们对每个数建立一条无向边，那么这条无向边应该连接什么呢，我们考虑每个数恰好有两个属性，分别是它属于的数组和它的值，这恰好与我们的约束连接了起来，于是考虑对每个数组和每个值建点。

建完点之后观察一下，由于每个值出现次数和数组长度均为偶数，因此每个点的度数也是偶数，整个图可以构成若干个欧拉回路，同时，由于边连接的点的属性不同，因此整个图还是一个二分图。

考虑直接给每个欧拉回路定向，可以发现欧拉回路对其上的每个点都有一个出度和一个入度的贡献，这恰好满足了两个约束条件，因为入度和出度的这两条边选择了不同的集合。

最后直接遍历图即可，注意因为我们是在唯一遍历每条边，因此遍历完边后要删去这条边和与之对应的反边，否则会 TLE。

1634 F. Fibonacci Additions

有两个长为 $n$ 在 $mod$ 下的数组 $A,B$ ，每次选择一个数组做区间加 Fib 数组的前若干项，问每次加完后是不是有 $A$ 与 $B$ 相等。

神秘思路题，首先等价于单个数组做区间加减，然后考虑 Fib 对差分数组的影响，但是一般的差分数组被影响的还是很多，于是不妨令 $C_i=A_i-A_{i-1}-A_{i-2}$ ，再考虑区间加的影响。

如果对 $[l,r]$ 区间加，即为 $C_l\leftarrow C_l+Fib_1,C_{r+1}\leftarrow C_{r+1}-Fib_{r+2-l},C_{r+2}\leftarrow C_{r+1}-Fib_{r+1-l}$ ，减类似

于是线性的维护 $C$ 数组中 $0$ 的个数即可。

1654 F. Minimal String Xoration

给你长 $2^n(n\le18)$ 的小写字母字符串 $s$ ，现在要找到等长的字典序最小的 $t$ ，满足至少存在一个 $j$ ，使得 $\forall i,t_i=s_{i\oplus j}$

发现不同的 $j$ 分别对应一个 $t$ ，考虑把所有 $t$ 排序得到最小的

和后缀排序很类似，令 $rk_{i,j}$ 表示 $\oplus i$ 时（也就是以 $i$ 位开头）在第 $j$ 轮的排名（比前 $2^j$ 位的结果）

考虑 $i$ 与 $k$ 在第 $j$ 轮大小时，先比 $rk_{i,j-1}$ 与 $rk_{k,j-1}$ ，若等，需要判 $rk_{i\oplus 2^{j-1},j-1}$ 与 $rk_{k\oplus 2^{j-1},j-1}$ 关系。

想的时候想了点没用的东西，如果建立一颗字典树，那么当前位的 $1$ 表示把这一层的子树全部 swap，但是由于相等的时候很难处理，所以没法比较平凡的按位贪心。

1656 F. Parametric MST

给你 $n$ 个绝对值小于 1e6 的整数序列 $a_i$ ，令定义在 $\mathbb R$ 上的 $K_n(t)$ 表示 $n$ 个点的无向带权完全图，任意两点 $u,v$ 有点权 $a_ua_v+t(a_u+a_v)$ ，求权值和最大的 MST，或者给出 MST 为正无穷。

观察到 $a_ua_v+t(a_u+a_v)=(a_u+t)(a_v+t)-t^2$ ，后面项可以被分离，那么考虑 $t$ 取某值时，有一部分 $a_i+t$ 是负数，一部分是正数，可以贪心的连边。

具体的，如果有正有负，最小的连所有正数，最大的连所有的负数，化简后发现和 $t$ 是呈线性的，可以通过前缀和 $O(1)$ 求出端点值。全负或者全正最大或者最小连所有点即可，这个时候判断 $t$ 系数的正负，可以看看 MST 是不是正无穷。

1644 F. Basis

给两个对整数序列的函数： $F(a,x)$ 表示将长为 $n$ 的整数序列 $a$ 每个元素复制 $x-1$ 份连接在此元素的后面，并截取前 $n$ 个元素作为返回结果； $G(a,x,y)$ 表示将序列所有的 $x,y$ 的值做一个对换。

如： $F([2,2,1,3,5],2)=[2,2,2,2,1],G([2,2,1,3,5],1,3)=[2,2,3,1,5]$

给你 $n,k$ ，设 $S=\{a|a_i \in \{1,2,\dots,k\},|a|=n\}$ ，求最少需要多少个属于 $S$ 的元素，能够通过上述两个函数生成 $S$ 中的所有元素，对 998… 取模

考虑两个函数的意义，可以发现 $G$ 实际上可以把数值随便换，只要原来相等现在仍相等即可。假设某个情况有 $i$ 个颜色，实际上就是对每个位置挑一种颜色，相当于把 $n$ 个有标号位置放到 $i$ 个无标号颜色里面，即 $S_2(n,i)$

考虑 $F$ 的意义，假设 $a_1\sim a_{\lceil \frac n x \rceil}$ 有 $i$ 个颜色，那么 $F(a,x)$ 实际上重复计算了 $S_2(n,i)$ 的部分，这启发我们进行容斥。

我们独立考虑每种颜色的情况，假设目前颜色数为 $i$ ，那么枚举延长倍数 $x$ 后，我们会钦定 $a_1\sim a_{\lceil \frac n x \rceil}$ 的颜色数为 $i$ 来考虑相应的贡献。

注意到 $x$ 倍时会重复计算其因子倍数的情况，例如 $x$ 取 6 时 $a_1 \sim a_{\lceil \frac n 6\rceil}$ 延长后一定是 $a_1 \sim a_{\lceil \frac n 2\rceil},a_1 \sim a_{\lceil \frac n 3\rceil},a_1 \sim a_n$ 的子集，算出相应的容斥系数后可以发现为 $\mu(x)$ .

那么有没有可能是其他倍数的子集？观察到 $i>1$ 时这是不发生的，这告诉我们需要特判单个颜色的情况。

由上，我们的答案即为

\sum_{x=1}^n\mu(x)\sum_{i=2}^{\min (\lceil\frac n x\rceil,k)}S_2(n,i)

借助第二类斯特林数行的做法，即可 $O(n\log^2n)$ 实现

Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.