题解

A 运算

给定 $n+1n+1$ 个整数 $a_{0}a\_0$ 到 $a_{n}a\_n$，其中 $a_0=0a\_0=0$，你可以在每两个数之间填上加，减，除，按位与，按位或，按位异或中的任意一个运算符（不可以填乘），然后不计优先级，从左至右进行运算，得到一个结果。求结果最大值。

这里的按位与，按位或，按位异或一个数为按位与，按位或，按位异或一个数的绝对值。除为向 $00$ 取整。

对于全部数据，$1\le n\le 5\times 10^5,-10^9\le a_i\le 10^{9}1\backslash le\; n\backslash le\; 5\backslash times\; 10^5,-10^9\backslash le\; a\_i\backslash le\; 10^9$。

题解

容易证明，答案为所有数绝对值的和。

B “经典”问题

给定一个序列，$mm$ 次查询区间的 mex 值，mex 表示最小的没出现过的自然数，$n,m\le 10^{5}n,m\backslash le\; 10^5$。显然可以使用经典算法轻易解决这个经典问题。

现在蒟蒻 djy 魔改了一下它，给定一个 $00$ 到 $n-1n-1$ 的排列，$mm$ 次查询区间的 mex 值，但是 $n,mn,m$ 变大了，你能帮帮他吗?

$n,m\le 10^{7}n,m\backslash le\; 10^7$，输入数据在程序内生成。

题解

答案为区间 $[1,l-1][1,l-1]$ 和区间 $[r+1,n][r+1,n]$ 的最小值。

证明：小于答案的数在区间外没出现过，因为排列每个数恰好出现一次，所以在区间出现过。答案在区间外出现过，在区间内没出现过。

C 维护序列

你要维护两个长度为 $nn$ 的序列 $a,ba,b$，支持以下两种操作：

1 l r k，表示对于每个 $i\in [l,r]i\backslash in\; [l,r]$ 执行 $kk$ 次以下操作：交换 $a_i,b_{i}a\_i,b\_i$，然后 $a_{i}a\_i$ 变为 $a_i+b_{i}a\_i+b\_i$。

2 x 查询 $a_{x}a\_x$ 和 $b_{x}b\_x$ 的值，分别对 $10^9+710^9+7$ 取模。

操作共 $mm$ 次。

$n,m,k\le 10^{5}n,m,k\backslash le\; 10^5$。

题解

考虑一个毫不相干的问题：如何不用数组递推斐波那契数列？可以用两个变量来表示当前项和上一项。这样看，递推k次时恰好就是一操作的内容。

所以我们要求的就是以初始序列作为第一项和第二项的广义斐波那契数列的两项。

这样我们只需要维护当前每个位置是第几项，然后查询时矩阵快速幂求解即可。区间加，单点查询，差分树状数组就行了。

D

题意： 你有一个 $r\times cr\times c$ 的六边形网格，一共有 $rr$ 行 $cc$ 列，第 $i(1\le i\le r)i(1\le i\le r)$ 行第 $j(1\le j\le c)j(1\le j\le c)$ 列的格子有一个权值 $A_{i,j}A\_\{i,j\}$。其中 $(i,j)(i,j)$ 相邻的格子为 $(i,j\mathrm{-}1),(i,j+1),(i\mathrm{-}1,j),(i\mathrm{-}1,j+1),(i+1,j\mathrm{-}1),(i+1,j)(i,j-1),(i,j+1),(i-1,j),(i-1,j+1),(i+1,j-1),(i+1,j)$ 其中存在的格子。 注意，你并不需要知道网格具体长什么样，只需要知道格子的邻接关系即可。 每次操作，你可以选择一个格子，然后将其权值加上 $11$。希望经过不超过 $kk$ 次操作之后，相邻格子差的最大值最小。输出这个最小值。 数据范围： $1\le r\times c\le 10^{5}1\backslash le\; r\backslash times\; c\; \backslash le\; 10^5$，$k\le 10^{18}k\backslash le\; 10^\{18\}$，$A_{i,j}\le 10^{12}A\_\{i,j\}\backslash le\; 10^\{12\}$。

题解

先二分答案，容易转化成要求出每个格子至少要多少，统计一下需要补到多少即可。 这部分如果使用 Dijkstra，那么有两个 log，不一定能过。 优化大概有这么些方法： 1. 一开始将所有点排完序。每次做的时候使用两个队列的技巧模拟Dijkstra。 2. 根据图的特殊性，两点之间一定存在一条标号先递增后递减，或者先递减后递增的路径。所以只要正反正反更新几次即可

E 刀虎二象性

沈阳大街今犹在，不见当年整活人。

维护一个数列 $aa$ ，这个数列初始为空。

对于这个数列 $aa$ ，总共有 $qq$ 次操作，每次操作分为如下五个种类：

1. 1 x，在数列末尾加一个数字
2. 2 x y，将数列中所有值为 $xx$ 的数的值替换成 $yy$
3. 3 x ，查询值为 $xx$ 的位置的个数
4. 4 x ，查询位置 $xx$ 上的数
5. 5 x y ，满足 $a[x]=a[y]a[x]=a[y]$ 求最早的使得 $a[x]=a[y]a[x]=a[y]$ 的时刻

我们定义每次操作 / 询问为一个时刻。

强制在线

$q\le 2\times 10^{5}q\backslash le\; 2\backslash times\; 10^5$。

题解

考虑维护一个森林，森林中的节点分为两类：

• 权值点，每个点表示一个权值。

• 位置点，每个点表示一个位置。

对于一个位置点，考虑使得该位置所在树的根节点的权值为该位置的权值。

如果一个权值在当前的森林中不是根节点，就在森林中新添加一个权值点。

那么对于第二种操作可以看成在森林中新添加一条边。

对于查询 $33$，考虑其对应的权值点是否为一棵树的根节点，如果不是则为 $00$，如果是相当于子树内位置点的个数。

对于查询 $44$，等价于查一个位置点所在树的根节点的权值。

对于查询 $55$，可以在每个点和树上的每条边上维护被加入时的时间戳，那么等价于查位置点树上路径的最大值。

使用 LCT 动态维护森林，复杂度 $O(q\log q)O(q\backslash log\; q)$。

F 抽奖

NaCly_Fish 去抽奖，每次抽到奖品的概率都是 ${\displaystyle \frac{a}{b}}\backslash dfrac\; ab$。

她想要 $mm$ 个奖品，于是她决定连续抽奖，直到自己拿够 $mm$ 个奖品为止。

设随机变量 $xx$ 为 NaCly_Fish 的抽奖次数，她很快就算出了 $xx$ 的数学期望值；但是她想知道 $x^{k}x^k$ 的数学期望值是多少。

她并不希望你进行太复杂的运算，故你只需要告诉她答案对 $998244353998244353$ 取模的值。

（$1\le k\le 10^{7}1\backslash le\; k\; \backslash le\; 10^7$，$1\le m\le 9\times 10^{8}1\backslash le\; m\; \backslash le\; 9\backslash times\; 10^8$，）

题解

考虑枚举每此抽到奖品需要的次数，恰好抽 $nn$ 次后中奖的概率就是 $(1-q{)}^{n-1}q(1-q)^\{n-1\}q$，就有计算式：

$E(x^k)=\frac{q^m}{(1-q{)}^m}{\sum }_{n_1=1}^{\mathrm{\infty }}{\sum }_{n_2=1}^{\mathrm{\infty }}\cdots {\sum }_{n_m=1}^{\mathrm{\infty }}{\left({\sum }_{i=1}^m{n}_i\right)}^k{\prod }_{j=1}^m(1-q{)}^{n_j}E(x^k)\; =\; \backslash frac\{q^m\}\{(1-q)^m\}\backslash sum\_\{n\_1=1\}^\{\backslash infty\}\backslash sum\_\{n\_2=1\}^\backslash infty\; \backslash cdots\backslash sum\_\{n\_m=1\}^\{\backslash infty\}\backslash left(\; \backslash sum\_\{i=1\}^m\; n\_i\backslash right)^k\backslash prod\_\{j=1\}^m(1-q)^\{n\_j\}$ 根据 $i^k=k![x^k]{\text{e}}^{ix}i^k=k![x^k]\backslash text\; e^\{ix\}$，答案就可以写为 $E(x^k)=\frac{q^m}{(1-q{)}^m}\left[\frac{x^k}{k!}\right]{\sum }_{n_1=1}^{\mathrm{\infty }}{\text{e}}^{n_{1}x}(1-q{)}^{n_1}{\sum }_{n_2=1}^{\mathrm{\infty }}{\text{e}}^{n_{2}x}(1-q{)}^{n_2}\cdots {\sum }_{n_m=1}^{\mathrm{\infty }}{\text{e}}^{n_{m}x}(1-q{)}^{n_m}E(x^k)=\; \backslash frac\{q^m\}\{(1-q)^m\}\backslash left[\; \backslash frac\{x^k\}\{k!\}\backslash right]\backslash sum\_\{n\_1=1\}^\{\backslash infty\}\backslash text\; e^\{n\_1x\}(1-q)^\{n\_1\}\backslash sum\_\{n\_2=1\}^\backslash infty\; \backslash text\; e^\{n\_2x\}(1-q)^\{n\_2\}\backslash cdots\backslash sum\_\{n\_m=1\}^\{\backslash infty\}\; \backslash text\; e^\{n\_mx\}(1-q)^\{n\_m\}$ 注意到这样各个和式之间就不相关了，可以直接写为各和式的乘积： $E(x^k)=\frac{q^m}{(1-q{)}^m}\left[\frac{x^k}{k!}\right]{(\frac{1}{1-(1-q){\text{e}}^x}-1)}^{m}E(x^k)\; =\; \backslash frac\{q^m\}\{(1-q)^m\}\backslash left[\; \backslash frac\{x^k\}\{k!\}\backslash right]\backslash left(\; \backslash frac\{1\}\{1-(1-q)\backslash text\; e^x\}-1\backslash right)^m$ 那么现在的问题就变为提取 $r^m{\text{e}}^{mx}(1-r{\text{e}}^x{)}^{-m}r^m\backslash text\; e^\{mx\}(1-r\backslash text\; e^x)^\{-m\}$ 的 $x^{k}x^k$ 系数，使用 FFT 就可以做到 $\mathrm{\Theta }(k\log k)\backslash Theta(k\; \backslash log\; k)$ 的时间复杂度，但这显然是不够的。

根据 EI 总结的一套方法，设 $F(x)=(x+1{)}^m(1-r(x+1){)}^{-m}F(x)=(x+1)^m(1-r(x+1))^\{-m\}$，所求即 $r^m[x^k]F({\text{e}}^x-1)r^m[x^k]F(\backslash text\; e^x-1)$。

由于 ${\text{e}}^x-1\backslash text\; e^x-1$ 没有常数项，所以次数高于 $x^{k}x^k$ 的项对于答案没有贡献，我们只需知道 $\mathcal{F}(x)=F(x)\mathrm{m}\mathrm{o}\mathrm{d}{x}^{k+1}\backslash mathcal\; F(x)\; =\; F(x)\; \backslash bmod\; x^\{k+1\}$，然后求 $[x^k]\mathcal{F}({\text{e}}^x-1)[x^k]\backslash mathcal\; F(\backslash text\; e^x-1)$ 即可。

直接这样算并没有优化复杂度，但 $\mathcal{F}(x)\backslash mathcal\; F(x)$ 的系数是可整式递推的，设 $\mathcal{G}(x)=\mathcal{F}(x-1)\backslash mathcal\; G(x)\; =\; \backslash mathcal\; F(x-1)$，则 $\mathcal{G}(x)\backslash mathcal\; G(x)$ 也是可整式递推的，其前 $kk$ 项系数可以 $\mathrm{\Theta }(k)\backslash Theta(k)$ 计算，再配合线性筛就可以计算出 $[x^k]\mathcal{G}({\text{e}}^x)[x^k]\backslash mathcal\; G(\backslash text\; e^x)$。

具体来讲，求导一下可以得到 $F(x)F(x)$ 的 ODE： $(1+x)(q-rx)F^{\mathrm{\prime }}(x)-m(r+q)F(x)=0(1+x)(q-rx)F\text{'}(x)\; -\; m(r+q)F(x)\; =\; 0$ 提取 $x^{n-1}x^\{n-1\}$ 系数： $nq{F}_n+(q-r)(n-1)F_{n-1}-r(n-2)F_{n-2}-m(r+q)F_{n-1}=0nqF\_n+(q-r)(n-1)F\_\{n-1\}-r(n-2)F\_\{n-2\}-m(r+q)F\_\{n-1\}=0$ 设 $f_n=[x^n]\mathcal{F}(x)f\_n=[x^n]\backslash mathcal\; F(x)$，$u=-(k+1)q{F}_{k+1}u=-(k+1)qF\_\{k+1\}$，$v=-rk{F}_{k}v=-rkF\_k$，就有 $nq{f}_n+(q-r)(n-1)f_{n-1}-r(n-2)f_{n-2}-m(r+q)f_{n-1}=[n=k+1]u+[n=k+2]vnqf\_n+(q-r)(n-1)f\_\{n-1\}-r(n-2)f\_\{n-2\}-m(r+q)f\_\{n-1\}=[n=k+1]u+[n=k+2]v$ 写做 ODE 就是 $(1+x)(q-rx){\mathcal{F}}^{\mathrm{\prime }}(x)-m(r+q)\mathcal{F}(x)=u{x}^k+v{x}^{k+1}(1+x)(q-rx)\backslash mathcal\; F\text{'}(x)-m(r+q)\backslash mathcal\; F(x)\; =\; ux^k+vx^\{k+1\}$ 做代换 $x=t-1x=t-1$，得到 $\mathcal{G}(t)\backslash mathcal\; G(t)$ 的 ODE： $t(q-r(t-1)){\mathcal{G}}^{\mathrm{\prime }}(t)-m(r+q)\mathcal{G}(t)=u(t-1{)}^k+v(t-1{)}^{k+1}t(q-r(t-1))\backslash mathcal\; G\text{'}(t)-m(r+q)\backslash mathcal\; G(t)\; =\; u(t-1)^k+v(t-1)^\{k+1\}$ 直接提取系数就能得到递推式，这里就不赘述了。

总时间复杂度 $\mathrm{\Theta }(k)\backslash Theta(k)$。