CF2150D Attraction Theory 题解

· · 题解

Update：

现在赋予 1 到 n 的每个点权值，它们形成一个数列 \{a_n\}，求对于所有操作后可能的 \{p_n\} 的 \displaystyle\sum_{i=1}^na_{p_i} 的值的总和对于 998244353 取模的结果。
数据范围：

Part 1：将题目问题转化：

这道题看起来就很数学，但是 \displaystyle\sum_{i=1}^na_{p_i} 的这个 a_{p_i} 限制了我们拆贡献之类的操作，考虑把它转化掉。
注意到 \forall i\in[1,n],p_i\in[1,n]，所以我们考虑将 \{p_n\} 映射到它的值域上。
更加具体地，令 \displaystyle t_i=\sum_{j=1}^n[p_j=i]，也就是说 t_i 是 \{p_n\} 中 i 的出现次数，那么现在我们容易将 \displaystyle\sum_{i=1}^na_{p_i} 转化为 \displaystyle\sum_{i=1}^na_it_i，容易发现 \{p_n\} 和 \{t_n\} 一一对应，问题得到了解决。

Part 2：对 \{t_n\} 发掘性质：

注意到 \displaystyle\sum_{i=1}^na_it_i 这个式子还是无从下手，这是因为我们没有对哪些 \{t_n\} 合法有一个具体的认知，我们不妨发掘一些合法的 \{t_n\} 的性质。

  1. 显而易见地，\exist 1\le L\le R\le n,\forall i\in[L,R],t_i>0,\forall i\notin[L,R],t_i=0，也就是说 t_i\ne 0 的 i 构成了一段区间。
    :::::success[证明]
    显然操作不会扩大人与人之间的间距，同时原来初始时 t_i\ne 0 的 i 就构成了一段区间，那么无论怎么操作都不会影响能否构成区间。
    实际上使用了数学归纳法的思想。
    :::::
  2. 假定有一个初始 \{t_n\} 序列，容易得到唯一一组满足性质 1 中限制的 L,R 以及原序列 \{p_n\}。这个 \{t_n\} 序列经过若干次操作后变为了 \{t'_n\}，同样得到类似的 L',R' 和原序列 \{p'_n\}，那么 \forall i\in[1,n],p'_i\in(L',R')\Rightarrow p_i\in(L,R)。
    :::::success[证明]
    考虑反证法。
    若 p_i\notin(L,R)（其实就是 p_i\in\{L,R\}），那么由于操作的性质，显然能推出 p'_i\notin(L',R')，与条件矛盾。
    :::::
  3. 对于每个 \{t_n\} 唯一一组满足性质 1 中限制的 L,R，都又能使得 \forall i\in(L,R),t_i\equiv 1\pmod 2。
    :::::success[证明]
    考虑数学归纳法。
    对于初始时 \forall i\in(L,R),t_i=1，性质显然成立。
    我们假设操作前序列符合性质，注意到多个原来不同位置上的人只会在被操作的位置上移动到同一位置，也就是说只会在被操作的位置上“合并”，所以我们仅需验证被操作位置的 t_i 的奇偶性即可。
    由于 2，所以 i 位置上的所有人以前都不在端点上，所以“合并”时一定是 pos-1,pos,pos+1 合并，三个奇数相加仍然是奇数。
    :::::

    Part 3：构造证明充分性：

    前面的性质 1,3 对于 \{t_n\} 的可能性作了限制，那么满足这些性质的是否就一定合法呢？
    :::::success[证明] 考虑构造。
    我们要构造出 \{t_n\}。

  4. 求出它的 L,R。
  5. 在位置 1 处进行 t_L 次操作。
  6. 在位置 n-t_L 处进行 t_R 次操作。
  8. 在位置 1 或 n 处进行若干次操作平移 \{t_n\}。
    :::::

    Part 4：大力分讨拆贡献：

    前面铺垫了这么多，我们终于要算答案了。
    注意到我们要枚举 t_L 和 t_R 的奇偶性，我们要先特判：

    • 我们直接枚举 $L$，$L$ 处的答案就是 $na_L$。
    • 根据 Part 3 的构造过程 5，对于 $R-L+1$ 相同的 $L,R$ 答案是类似的，只是所乘的 $a_i$ 不同，所以我们考虑枚举 $R-L+1$，然后枚举 $x,y\in\{1,2\}$，表示 $t_L$ 和 $t_R$ 的奇偶性。 容易发现，此时对于存在一个 $\{f_n\}$ 满足 $t_L=2f_L+x$ 且 $t_R=2f_R+y$ 同时 $\forall i\in(L,R),t_i=2f_i+1$ 且 $\forall i\notin[L,R],f_i=0$，容易发现 $f_i$ 和 $t_i$ 一一对应，为了方便计算我们后文将计算 $\{f_n\}$ 的数量，再来计算贡献。 容易发现，$\displaystyle\sum_{i=L}^R2f_i=n-(x-1)-(y-1)-(R-L+1)=n-x-y+(R-L+1)+2$，我们记为 $res$，那么我们特判掉 $res<0$ 或 $res\equiv 1\pmod 2$ 的情况，容易发现 $\displaystyle\sum_{i=L}^Rf_i=\frac{res}{2}$，那么 $\{f_n\}$ 的数量可以通过插板法计算，为 $\displaystyle\binom{R-L+\frac{res}{2}}{R-L}$，这个可以预处理阶乘和逆元计算。 $\{f_n\}$ 的数量算出来了我们还不能直接得出答案，注意到 $\forall i\in(L,R)$ 部分任意顺序的 $\{f_n\}$ 均合法，所以 $f_i$ 的期望为 $\dfrac{res}{2(R-L+1)}$，我们也容易得到 $t_i$ 的期望，$t_i$ 的期望乘 $\{f_n\}$（$\{t_n\}$）的数量再乘长度为 $R-L+1$ 的 $\{a_n\}$ 的连续子序列和的总和就是 $R-L+1$ 的答案，所以我们还差最后一步：算长度为 $R-L+1$ 的 $\{a_n\}$ 的连续子序列和的总和。 这个东西其实不难，直接推导： $$\begin{aligned}\sum_{l=1}^{n-R+L}\sum_{i=l}^{l+R-L}a_i&=\sum_{l=1}^{n-R+L}sum_{l+R-L}-sum_{i-1}\\&=(\sum_{l=1}^{n-R+L}sum_{l+R-L})-(\sum_{l=1}^{n-R+L}sum_{i-1})\\&=sum^2_n-sum^2_{R-L}-sum^2_{n-R+L-1}\end{aligned}$$ 其中 $\{sum_n\}$ 是 $\{a_n\}$ 的前缀和，$\{sum^2_n\}$ 是 $\{sum_n\}$ 的前缀和，直接预处理即可。

太好了我们终于做完了！
时间复杂度为 \Theta(n\log V)（线性预处理逆元可以做到 \Theta(n)），空间复杂度为 \Theta(n)。

code
:::::warning[坑点] 看看谁预处理阶乘没有预处理到 2n？
看看谁取模取少了？
看看谁算前缀和没加模数？
:::::