本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-08-17 11:58:56

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

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

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 很简单题

题意

$h$ 个点 $n$ 条边，$q$ 次询问在边权为 $0$ 的完全图中加入 $[l,r]$ 内的边形成的最大生成树。$h\le 10,n,q\le 5\times 10^5$。

题解

Sol.1

直接暴力上线段树，每个节点上记录该区间内最小生成森林的所有边，至多 $h$ 条，合并时用 $2h$ 条边跑最小生成树即可。时间复杂度 $O(n\log nh\lpha(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\lpha(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)$。