25.07-SDSC 模拟赛题解

· · 题解

风物长宜放眼量，心胸要开阔。

只写了感觉比较有意义的题。

D1T1 最大公约数

题意

给出长为 n 的序列 a_i，可进行一次区间加 k 操作，求操作后全局 gcd 的最大值。多测，T\le 5,n\le5\times10^5,a_i,k\le 10^{18}。

题解

观察一下答案结构，是前后缀各一段再拼上中间加 k 的形式。又由于前缀 GCD 只有 O(\log V) 段不同取值，猜想每段有用的 l 很少。事实的确如此，若结尾在 [L,R] 内的前缀 GCD 均为 g，则 l=R+1 在 l\in [L+1,R+1] 中一定最优。证明考虑最终答案是 g_L,g_M,g_R 三者的 GCD，而这段 l 对应的 g_L 均为 g，此时把尽可能少的数划到中间一定更优。同理也只有 O(\log V) 个有用的 r。

可以直接类似枚举所有有用的 l，同时只在有用的 r 处统计答案。这里由于 GCD 不变时函数只会运行 O(1) 次，直接维护中间部分 GCD 就是 O(n+\log V) 的。由于统计答案时还要算一次 GCD，总复杂度为 O(n\log V+\log ^3V)。

也可以直接暴力枚举所有合法对 [l,r]，g_L 和 g_R 容易前后缀预处理。考虑使用 ST 表维护区间 GCD，复杂度 O(n\log^2V+\log^3 V)，但 chb 说这个是均摊 O(n\log V) 的，不懂，反正不好过。

事实上注意到关键点只有 O(\log V) 个，考虑只对这些点建 ST 表，即 w_i 表示两个关键点之间的 GCD。预处理 w_i 只需 O(n\log V) 的复杂度，对 w 建出 ST 表后枚举区间即可，总复杂度也是 O(n\log V+\log^3V)。

D1T2 回家路径

题意

给出 n 个点 m 条边的有向图，经过每条边需要花费 w_i 元。初始有 p 元钱，在 i 点上每次可赚 a_i 元，求可从 1 走到 n 的最小赚钱次数。多测，T\le 5,n\le 800,m\le 3000,p,a,w_i\le 10^9。

题解

考虑路径确定时如何赚钱最优，显然只会在 a_i 前缀最大值处赚钱，否则一定可以在前面的点赚更多的钱，且不会导致方案非法。因此可 Dijkstra 预处理出所有点对间的最短路 d_{i,j}，根据上面的结论枚举前缀最大值，因此只会进行 a_i<a_j 的 i\rightarrow j 转移。状态内记录 (c,t)，表示到该点至少需要赚 c 次钱，此时最多剩余 t 元。显然在 c 最小的前提下令 t 最大最优，因为 c 大时完全可以将多出的次数放到后面更大的前缀最大值处赚。因此按 a_i 排序后可直接转移，每次多赚若干次钱并计算新的 (c',t') 即可，时间复杂度 O(nm\log m+n^2)。

原题

P13534。

D1T3 树上划分

题意

给定一棵树，对其划分连通块，最大化每个连通块的次大值之和。n\le 5\times 10^5,a_i\le 10^9。

题解

考虑最终连通块的结构，注意到每个连通块只保留最大值和次大值之间的路径即可，其他点可以放到别的连通块中使得答案不降。因此存在最优解为路径划分，问题转化为划分路径，求每条路径两端点较小值之和的最大值。由于取到更小的值一定不优，这样求出的结果不会超过答案，显然也能取到最终答案。

考虑对此进行树形 DP，设 f_{u,i} 表示以 u 为根的子树中，u 点向下连到了值为 i 的点，且该路径未完全确定，子树内其他路径权值和的最大值，g_u 表示 u 点已被占用时子树内权值和最大值。转移时依次合并每个子树 v，有 f_{u,i}=\max(f_{u,i}+g_v,f_{v,i}+s),g_u=\max(g_u+g_v,f_{u,i}+f_{v,j}+\min(i,j))，其中 s 表示之前合并过的子树 g 的和，使用一些前后缀优化可以做到 O(nV)。

使用线段树合并优化该 DP，对 f 的 i 一维开线段树存储 DP 值，转移时将两线段树内的元素带权合并起来即可。g_u 需要求 \max (f_{u,i}+f_{v,j}+\min(i,j))，这个可以在合并过程中处理，在每次递归到子树之前用左右子树更新答案即可，细节较多，时间复杂度 O(n\log n)。

D1T4 还原排列

题意

给出序列 b，可还原出一个排列 p，使得 \forall i,\sum_{j<i}[p_j>p_i]=b_i，即其前面有 j 个更大的数。要求支持单点修改，询问某个 p_i 可能的最小值，保证有解。n,q\le 2\times 10^5。

题解

考虑如何还原，可以正序处理，b_i 即其在前 i 个数中的相对排名；也可倒序处理，维护目前剩余的值，即可找到第 b_i+1 大的值赋给 p_i。由此可见排列是唯一的，题意中的最小值只是诈骗，上面也给出了一种单次 O(n\log n) 的做法。

考虑先优化到单次 O(n)，注意到只询问 p_i 一个值，上面的做法却还原出了整个排列，比较浪费。考虑从 i 不断向后扫，并维护 r 表示目前比 p_i 大的数有多少个。那么扫到 b_j 时若 b_j\le r，一定有 p_j>p_i，给 r 加上一；否则 r 不变。最终 n-r 即为所求。

再用数据结构优化该过程，注意到每个 b_i 会使后缀的一段 r 加一，若把 (r,r') 画在坐标系上，会以 b_i 为分界线形成两段一次函数。此时若再经过 b_{i+1}，会再将 r'\ge b_{i+1} 的部分向上平移，从而得到三段一次函数。据此经过 c 个数时，会形成 c 段一次函数。

考虑快速合并两组一次函数。用 f_c,g_d 分别表示两组，每个值表示该处比上个函数该处大 1，作为新一段的开头，也即 [f_i,f_{i+1}) 内的数经过后会加 i。则新的 h_i=\min_{j+k=i}(f_j,g_k-j)。注意到若 h_i 在 (j,k) 处最优，则 h_{i+1} 一定在 (j+1,k) 或 (j,k+1) 上最优，因此可类似归并合并，复杂度 O(c+d)。

这样就可以直接上线段树维护区间函数，线段树的 pushup 复杂度为 O(len)，单点修改时要重新向上合并到根，复杂度 O(n)，查询时可直接在 O(\log n) 个节点的函数上依次二分，总复杂度为 O(q(n+\log ^2n))。

由于修改复杂度远大于查询，考虑用分块平衡复杂度。将序列每 B 个元素分一块，块内用线段树维护区间函数。这样修改复杂度降到 O(B)，询问时先将本块内的单点暴力扫完，再依次在后面的 O(\frac nB) 个块上二分处理即可。总复杂度为 O(q(B+\frac {n\log n}B))，平衡至 B=\sqrt{n\log n} 得到最优复杂度 O(q\sqrt{n\log n})。

原题

CF1540D。

D2T4 树上监控

题意

给定一棵树，每个点有价值 a_i。现要在至多 k 个点上放置监控，监控可以观测到距离不超过 r 的所有点，求被观测到的节点价值和的最大值。多测，T\le 10,k\le n\le 10^3,r\le 10^3,1\le a_i\le 10^6。

题解

注意到 kr\ge n 时，一定能将整棵树全部覆盖，方式是找到深度最深的叶子，并在其 r 级祖先上放置监控，这至少会删掉该祖先子树中的至少 r 个点。因此放 k 次一定能覆盖完，只需要解决 kr<n 的问题。

然而 DP 状态难以设计，原因是覆盖距离 r 导致可能被父亲方向很远的点覆盖，因此考虑预先钦定每个点最终是否被覆盖，设 f_{u,i,x_1,x_2} 表示 u 子树内放置了 i 个监控，最深的钦定却未被覆盖的点距 u 点 x_1，最浅的监控距 u 点 x_2 时子树内最大贡献值。

显然 x_1+x_2>r 的状态才有意义，否则不会未被覆盖。另外此时若 x_1 存在，则子树外一定会放一个监控覆盖到它，且其在子树外的覆盖范围不小于子树内任意一个监控。因此此时不需要记录 x_2，之后用子树外更优的进行覆盖即可。

于是 x_1 不存在时记录 x_2，x_1 存在时只记 f_1，因此设 f_{u,i,x_1},g_{u,i,x_2} 分别表示两种情况下 u 子树内放 i 个监控的最大值。每次拼上一个子树，写出转移式后可以发现新的 x 值一定为 x 或 x+1，且另一个值有前后缀限制。因此对每个 (u,x) 预处理前后缀 max 值优化转移，可以做到每个状态 O(1)，总复杂度根据树形背包为 O(nrk)，根据前面的性质不会超过 O(n^2)，具体转移式此处略去。

原题

P4845。

D3T3 耳后的呼吸

题意

有 n 个开区间，保证存在一个公共点，问多少次将某区间平移 1 个单位后能使其两两不交。n\le 5000。

题解

设公共点为 x，则先整体向左平移 x，使得存在 0 为公共点。若 n 为奇数则会把除中间区间外的区间平分到两边，这时中间区间不需要移动；若 n 为偶数可添加一个区间 l=r=0，显然其也不会移动。推一推式子发现若左右各 c_1,c_2 个区间，最终代价为 c_2r_m-c_1l_m+\sum_{i=0}^{c_2-1} i\cdot len_i-\sum_{i=0}^{c_1-1} i\times len_{i}，其中每部分按照 len_i 降序排序最优，在数轴上即越长的区间越远离原点，这也能解释 c_1=c_2 最优。

据此可直接枚举不动的区间，并 DP 设 f_{i,j} 表示前 i 个区间选了 j 个在左的最小代价，时间复杂度 O(n^3)。然而发现中间区间只会决定 l_m,r_m 的取值，因此直接设 f_{i,j,0/1} 表示是否已经选出中间区间时的最小代价即可，时间复杂度 O(n^2)。

D4T2 很简单题

题意

#### 题解 ##### Sol.1 直接暴力上线段树，每个节点上记录该区间内最小生成森林的所有边，至多 $h$ 条，合并时用 $2h$ 条边跑最小生成树即可。时间复杂度 $O(n\log nh\alpha(h))$，由于常数较大，跑不过。 ##### Sol.2 用 $h^2$ 个 ST 表维护每种边的最大权值，直接维护需要 $O(h^2n\log n)$ 的空间，会爆。因此改为对每个询问维护 $h^2$ 种边的最大值，然后枚举每种边，建出 ST 表后对所有询问更新，空间复杂度优化到 $O(qh^2+n\log n)$。对每个询问用 $h^2$ 条边跑 Prim，时间复杂度为 $O(h^2n\log n+qh^2)$。 ##### Sol.3 Sol.1 中的 $h^2$ 个 ST 表内其实总共只有 $n$ 个元素，因此可以只建大小为 $cnt$ 的 ST 表，查询前映射过去。由于总元素个数有保证，建 ST 表的总时空复杂度为 $O(n\log n)$。比较暴力的映射方式是记录出现的位置，从而二分出左右端点，时间复杂度 $O(qh^2\log n)$，跑不过。 考虑去掉二分，直接对每种边开两个长为 $n$ 的数组，记录每个位置左边第一条和右边第一条该种边的编号即可，空间复杂度 $O(h^2n+n\log n)$，时间复杂度 $O(n\log n+h^2n+qh^2)$。 ##### Sol.4 是另一种优化取最小值的方式。考虑直接对边的编号 $[1,n]$ 分治，每次处理所有跨过中点 $mid$ 的所有询问，再把其余询问递归下去处理。具体地，每种边在 $[l,mid]$ 内处理一个后缀最小值，$[mid+1,r]$ 内处理一个前缀最小值，询问时把前后缀拼起来即可得到每种边的最小权值，最后同样再跑 Prim 即可。空间复杂度 $O(h^2n)$，时间复杂度 $O(h^2n\log n+qh^2)$。 ##### Sol.5 是 chb 的做法。将 Sol.4 的分治与 Sol.1 的维护方式结合起来，每次预处理前后缀最小生成树内的边。这时每次只会加一条边，因此不需要重跑 Kruskal，只需要在原树中 DFS 求路径最大值，并试图用新边替代最大边即可，复杂度 $O(h)$。询问时将前后缀 Kruskal 拼起来得到答案。时间复杂度 $O(hn\log n+qh\alpha(h))$。值得一提的是本题的 $\log n>h$，因此本做法算复杂度可能没有 Sol.3 优。 ### D4T4 特简单题 #### 题意 维护一个环，每个点的贡献为经过的 $a$ 最大值乘 $a_i$，需要支持区间覆盖，区间修改，查询给出 $i,z$，询问从 $i$ 开始走到第一个贡献大于 $z$ 的点。$n,q\le 2\times 10^5$。 #### 题解 下文中所有 $p$ 均表示前面走过的最大值。 考虑使用数据结构维护每个区域的贡献，再在该数据结构上二分。由于某个区域的贡献会受到前面最大值的影响，考虑使用单侧递归线段树。在每个节点上维护区间长度 $l$，$a_i$ 的最大值 $x$ 以及只经过该区间的总贡献 $w=\sum a_ip_i$，区间修改为 $k$ 时有 $x=k,w=lk^2$。 然而区间加只维护这些是不够的，区间加 $k$ 时对 $w$ 拆开 $\sum(p_i+k)(a_i+k)$ 得到 $\sum p_ia_i+kp_i+ka_i+k^2$，因此需要维护 $s=\sum a_i,d=\sum p_i$，即有 $w'=w+kd+ks+lk^2$。$s,d$ 修改为 $k$ 时均会变成 $lk$，区间加时均会增加 $lk$，就实现了所有的区间修改。 因此可以类似普通线段树用两个懒标记维护，注意覆盖标记会清空加标记，区间加时若有覆盖标记则加给覆盖标记，懒标记的下传也是容易的。现在需要实现的是 pushup 合并两个区间的操作，这种贡献与前面值有关的合并需要单侧递归。 具体地，设 $lc,rc$ 为线段树上左右儿子，现需合并 $L=lc_u,R=rc_u$ 的信息到 $u$。显然 $L$ 的信息均不变，而 $R$ 的信息可能会受到 $x_L$ 的影响。考虑再将 $R$ 分成 $lc_R$ 和 $rc_{R}$ 两部分，若 $x_{L}\ge x_{lc_R}$，则 $lc_{R}$ 内均以 $x_{L}$ 为 $p$，容易计算，因此记录 $x_L$ 并递归到 $rc_{R}$ 计算贡献；否则 $x_L<x_{lc_R}$，$x_L$ 一定无法越过 $lc_R$，$rc_R$ 的贡献为其在 $R$ 节点内的贡献，可用 $w_R-w_{lc_R}$ 计算，因此记录 $x_L$ 并递归到 $lc_R$ 计算贡献。 每次只会向左右子树中的一个递归，因此单次 pushup 的复杂度是 $O(\log n)$ 的。实现上只需要写成函数，对某节点传入一个前面经过的最大值 $p$，返回其内部考虑上前面的 $p$ 时的信息。上面其实就是调用 $(R,x_L)$ 的过程，具体可能要对 $d,w$ 分别写函数。 这样就以单次修改 $O(\log^2n)$ 的复杂度维护出了任意区间的信息。询问时考虑在线段树上二分，先求出能走到第一圈的哪个位置，过程中还是要带着前面的最大值，需要将该值传到函数里 $O(\log n)$ 确定当前节点的贡献。后面部分需求出最后一圈走到哪个位置，这里只对 $s$ 二分即可。实现起来细节比较多，还要考虑跨过环的情况，时间复杂度 $O(q\log ^2n)$。 ### D5T1 以史为鉴之习 #### 题意 给出一个长为 $n$ 序列 $a$，$q$ 次询问 $[l,r]$ 区间内数的乘积是否是完全平方数。$n,q\le 2\times 10^5,a_i\le 10^6$。 #### 题解 区间乘积为完全平方数当且仅当所有质因子的次数均是 $3$ 的倍数，考虑直接使用哈希，对每个前缀所有质因子的次数对 $3$ 取模的结果计算出哈希值 $s_i$，则 $[l,r]$ 合法当且仅当 $s_r=s_{l-1}$，时间复杂度应该可以线性。 也可以用莫队做，直接暴力维护所有质因子的次数，同时记录变量表示目前次数不为 $3$ 的质因子个数，每次区间变化就对 $\omega(a_i)$ 个质因子修改，时间复杂度 $O(n\sqrt q\omega(V))$。然而可以接受枚举 $\sqrt V=1000$ 以内的质因子，对这些用前缀和暴力枚举，之后只剩至多一个大于 $\sqrt V$ 的质因子，只对这个进行莫队即可，时间复杂度 $O((n+q)\sqrt V+n\sqrt q)$，事实上质因子个数远小于 $\sqrt V$。 ### D5T4 业报插翅难逃 #### 题意 给出一个序列 $a_i$，求有多少种重排方式使得相邻两数之积均不超过 $w$。$n\le2000,\left|a_i\right|\le 10^9,2\le w\le 10^9$。在 $a_i\ge 0 $ 时 $n\le 10^6$。 #### 题解 先考虑 $a_i\ge 0$ 怎么做，发现原来的限制很抽象。考虑构造一个排列 $p$，使得 $\forall i\in[1,n]$，要么 $\forall j<i,a_{p_i}a_{p_j}\le w$，要么 $\forall j<i,a_{p_i}a_{p_j}\gt w$，再按照这个顺序加入就会好做很多。具体构造考虑先按 $a_i$ 从小到大排序，此时若 $a_1a_n\le w$，则 $a_1$ 与任意数相乘均合法，将其放到结尾并删除；否则 $a_n$ 与任意数相乘均不合法，同样放到结尾并删除。这样就构造出了一个符合要求的排列。 之后考虑 DP，设 $f_{i,j}$ 表示考虑了前 $i$ 个数，目前还有 $j$ 个连续段的方案数。若新开一个连续段有转移 $f_{i+1,j+1}\leftarrow (j+1)f_{i,j}$，当某个数与前面均不合法时只能进行这种转移。若合并两个连续段有转移 $f_{i+1,j-1}\leftarrow (j-1)f_{i,j}$，若接在某连续段两边有转移 $f_{i+1,j}\leftarrow (2j)f_{i,j}$，答案为 $f_{n,1}$，时间复杂度 $O(n^2)$。 当正负均有时，由于异号相乘为负一定合法，直接分两组分别进行上述 DP，之后枚举两种的组数拼起来，若组数相等则乘 $2$，相差 $1$ 则不乘，对方案数求和即为答案，时间复杂度仍为 $O(n^2)$。 对于 $a_i\ge 0$ 还有一种神秘做法，考虑先按 $a_i$ 排序，并对每个数决策其前驱，则每个数能取前 $p_i$ 个数。之后倒着枚举所有 $p_i$，则其一定递增，因此有 $p_i-(n-i)+1$ 个可选的数（包括空，代表其为开头）。然而前驱不能选自己，因此容斥钦定 $S$ 中的数前驱选自己，其他不管。 这时答案为 $(-1)^{\left|S \right|}\prod_{i\notin S} p_i-(n-i)+1$，之后发现这个跟 $\prod p_i-(n-i)+1-[p_i\ge i]$ 等价，证明考虑把该式前后分开，并展开乘法就是前面的式子。因此答案为 $\prod p_i-n+i+[p_i<i]$，时间复杂度 $O(n)$。 ### D6T1 氧气 #### 题意 给出一个序列 $a$，要求从中选择 $k$ 个长为质数且不相交的子段，最大化所有子段和的最小值。$k\le n\le 2\times 10^5,\left|a_i\right|\le 1000$，且保证 $a_i$ 在范围内随机生成。 #### 题解 先二分最小值，之后要求每段的和均不小于该值。之后从左往右贪心，到新位置 $i$ 且上段结尾为 $k$ 时，若存在 $j\in[k,i)$ 使得 $s_i-s_j\ge mid$ 且 $i-j$ 为质数，则可将 $[j+1,i]$ 划分为新的一段，暴力做这个过程需要 $O(n^2\log (nV))$ 的复杂度。 考虑加速这个过程，注意到要求 $s_j\le s_i-mid$，因此满足条件的 $s_j$ 是一段前缀。因此将 $(s_j,j)$ 按 $s_j$ 排序存到 set 里，每次暴力从 set 开头依次取出元素检查，若 $s_j$ 已不合法则停止，否则若 $i-j$ 为质数就将答案加 $1$ 并清空 set，再进行后面的操作。 由于整个序列是随机生成的，因此 $s$ 数组的排名也可以认为是随机的，因此期望 $O(\log n)$ 次可以取到一个 $i-j$ 是质数的 $j$。同时从 set 开头取 $c$ 个元素的复杂度为 $O(\max(\log n,c))$，因此时间复杂度为 $O(n\log n\log (nV))$。 ### D6T2 bmbmbm #### 题意 $k$ 维空间，每一维大小均为 $n$，求其中 $m$ 个超立方体两两不交的方案数，要求每个立方体每一维均满足 $l<r$。取模，$n,k\le10^9,m\le6$。 #### 题解 首先两个立方体有交当且仅当它们每一维都有交，因此考虑在维度上 DP，即一维一维考虑。由于维度数 $k$ 过大，或许需要使用矩阵快速幂优化。考虑设 $f_{i,S}$ 表示考虑了 $i$ 个维度，$S$ 中为 $1$ 的位对应的二元组 $(i,j)$ 满足 $i,j$ 在前面的维度均有交，其余二元组已经无交的方案数。$S$ 的长度为二元组个数 $e=\frac{m(m-1)}2\le 15$，状态共有 $2^{15}=32768$ 个，转移式为 $f_{i,S}\times g_T\rightarrow f_{i+1,S\cap T}$，即枚举该维相交状态 $T$，其中 $g_T$ 表示一维内相交状态为 $T$ 的方案数。 需要预处理出 $g_T$，这里使用暴力搜索。由于维度大小 $n$ 也很大，考虑拿出其中作为区间端点的关键点，显然个数在 $[2,2m]$ 内。首先枚举关键点个数 $len$，再钦定顺序为先按左端点从小到大，再按右端点从小到大排序，同时要求不能有关键点没被选过。加上这些剪枝后跑得飞快，在 $m=6$ 时没有超过 150ms。 这样我们就得到了所有只保留关键点的区间方案，也容易计算出其对应的原问题方案数和相交情况 $T$，注意这里原问题方案数为 $n\choose len$ 乘上不同区间的多重集排列数。这样所有方案的方案数之和为 ${[\frac{n(n-1)}2]}^m$，即所有不同的区间选择方案。然而由于顺序已被钦定，还是难以推到每个 $g_T$ 的具体值。这里考虑对于两种状态 $S,T$，若忽略其编号后形态相同，则这两种状态本质相同，也有 $f_{i,S}=f_{i,T}$ 和 $g_{S}=g_T$。因此再写一个搜索搜出所有等价类，共 $c=156$ 种。具体实现上先枚举所有状态，再阶乘枚举置换即可。以下记 $S$ 所在的等价类为 $id_S$。 之后设 $h_i$ 表示 $i$ 等价类内的 $g_T$ 之和，$t_i$ 表示 $i$ 等价类内的状态个数。这样先让上一段中提到的相交情况 $T$ 贡献到 $h_{id_T}$，最后再令 $g_T=\frac {h_{id_T}}{t_{id_T}}$ 即可，由于等价类内数量相同，该式一定成立。同时等价类数量 $c$ 也已经能接受 $O(c^3\log k)$ 的复杂度，直接套矩阵快速幂优化即可，实现上有诸多细节。另外求出 $g_T$ 后，由于转移形如 And 卷积，可以 FMT/FWT 后直接快速幂计算，可做到 $O(2^e(e+\log k))$ 的复杂度，会快一些。 ### D6T3 ゆきこ #### 题意 对于一个排列 $p$，设 $f(p)=\sum\min(i-l_i,r_i-i)$，其中 $l_i,r_i$ 分别表示 $i$ 左右第一个比其大的位置。$T$ 次询问给出 $n,x$，求有多少个长为 $n$ 的排列 $p$ 满足 $f(p)=x$，对某模数 $P$ 取模。$n\le 300,x\le 10^9,T\le 10$。 #### 题解 先考虑 $f(p)$ 的上界，设 $g_n$ 表示长为 $n$ 的排列 $f(p)$ 最大值，枚举最大值位置有 $g_n=\max_{i=1}^n(g_{i-1}+g_{n-i}+\min(n-i+1,i))$。该过程类似启发式合并，因此 $g_n$ 不会超过 $O(n\log n)$ 级别，事实上常数很小。 设 $f_{n,i}$ 表示长为 $n$ 且 $f(p)=i$ 的排列数量，则有 $f_{n,i}=\sum_{j=1}^n \sum_{k=0}^if_{j-1,k}\times f_{n-j,i-k-\min(n-j+1,j)}\times {n\choose j-1}$，复杂度为 $O(n^4\log^2n)$，无法通过。注意到第二维全是加起来，且大小并不大，考虑改成用多项式维护 DP 值，即 $F_n$ 表示长为 $n$ 的排列 $x^{f(p)}$ 之和，是一个 $O(n\log n)$ 次多项式，暴力转移就是上面的式子。 考虑放弃维护整个多项式，而是只维护多项式实际值，可以避免 $O(n^2\log ^2n)$ 的转移复杂度。由于次数 $k$ 为 $O(n\log n)$，只需要知道 $(k+1)$ 个实际值即可还原其系数，因此维护这么多个值即可。设 $h_{n,x}$ 表示 $F_n$ 在 $x$ 处的取值，转移即为 $h_{n,x}=\sum_{i=1}^n h_{i-1,x}\times h_{n-i,x}\times x^{\min(i-1,n-i)}\times {n\choose i-1}$，这样复杂度变成 $O(n^3\log n)$，跟原来相比转移优化到了 $O(n)$。 这样询问 $n,x$ 时，用 $h_n$ 的若干值拉格朗日插值还原出 $F_n$，$x$ 次项系数即为答案。单次还原是 $n^2\log^2 n$ 的，因此总复杂度为 $O(n^3\log n+Tn^2\log^2n)$。 ### D7T1 Were #### 题意 给定 $x,k$，求经过若干次求数位和或加 $k$ 操作后能变成的最小值，以及变成该值的最少操作次数。多组数据，$T\le 10^3,x,k\le 10^{15}$。 #### 题解 注意到求数位和不会改变对 $9$ 取模的值，因此最终最小值一定为 $\min_{i=0}^8 w(x+ik)$，第一问答案就有了。同时 $10^{16}$ 以内的数最多取 $3$ 次数位和就只剩一位了，因此总操作次数 $c\le8+3=11$，枚举所有操作序列即可，复杂度 $O(Tc\cdot2^c)$。