### 1001 特殊处理 $n \leq 2$ 的情况。当 $n=k$ 时构造是容易的，当 $k \bmod 2 = 1$ 时可以发现字符串 $ababab\cdots$ 的长度为 $n$ 的前缀总是满足题设条件，故答案为 Yes。对于其他情况，即 $n>k$ 且 $k \bmod 2 = 0$ 的情况，可以将回文串条件可以导出的字符之间相等关系以边的方式画出来，容易证明字符之间总是两两相等，故答案为 No。 ### 1002 首先一个算式肯定是加法和乘法交替的。对于每组连续的加法或者乘法，如果组内的元素是相同的，那么运算的结果也是一样的。假设分成了 $x$ 组加法和 $y$ 组乘法，满足 $|x-y|\leq 1$，那么加法和乘法的分组都是独立的。问题等价于将 $n$ 个有标号的球分到 $m$ 个有标号的集合里面，使得每个集合都是非空的。这个问题可以用第二类斯特灵数简单解决。 所以总的时间复杂度是 $O(m^2+Tm)$ 的。 ### 1003 答案上界显然是 $\sum_{i=1}^n b_i$，即每次操作都让一个点的 $b_i$ 减去 1。考虑在这样的操作基础上将若干次操作合并为一次合法的操作从而减少总操作次数。在树上 dfs，对于每个节点维护其子树尽可能合并后当前节点还有多少个操作能和父亲合并，每个节点计算完所有儿子的子树的答案后贪心地与儿子合并操作。可以发现在可以与儿子合并操作的前提下与儿子合并总是不会比与父亲合并差，所以这样贪心是正确的。记录合并操作次数和即可求得答案。 ### 1004 对于一个确定的序列设 $w_{l,r} = \sum_{i=l}^r \sum_{j=l}^r \mathrm{dist}(a_i,a_j)$，对于一个给定的序列 $\{a_1,a_2,\cdots,a_n\}$ 容易设计动态规划 $f_{i,j}$ 表示对区间 $[i,j]$ 建立线段树的最小暴跳次数，转移枚举 $\mathrm{mid}$ 的取值，有 $f_{i,j} = \min_{mid=l}^{r-1}f_{l,mid}+f_{mid+1,r}+w_{l,r}$。可以注意到 $w_{l,r}$ 满足四边形不等式，故 $f_{i,j}$ 的转移满足决策单调性，即设 $k_{i,j}$ 表示 $f_{i,j}$ 的转移中取到最小值的 $\mathrm{mid}$ 取值，则 $k_{i,j-1} \leq k_{i,j} \leq k_{i+1,j}$。按照长度依次转移，转移 $f_{i,j}$ 时只枚举区间 $[k_{i,j-1},k_{i+1,j}]$ 中的转移点，复杂度为 $O(n^2)$。对于加入版本的操作，建立出操作树在上面 dfs，每次相当于加入一个元素，新增一列 dp 数组。这一列数组的转移仍然满足决策单调性，使用单调栈求解。需要注意这里不能使用枚举转移点的方式优化，因为其是均摊的，可以被卡到高复杂度。精细实现 $w_{l,r}$ 的求解即可做到 $O(T(m^2+n^2+nr\log n))$ std 1s, 好像时限开大了被暴力过了。 ### 1005 ~~根据B题的结果，如果直接搜索本质不同的方法，会比较难在时限内通过。~~ 好像直接搜索就行了啊？ 注意到，假设我们枚举完乘法的顺序，那么我们每个加法操作的贡献只和它们的位置相关，也就是插在哪几个乘法之间，并且是独立的。所以等价于每个加法操作有若干种选择，你要选择数字加起来使得 $\bmod p$ 最小。那么可以用 meet in middle 的方法解决。 然后如果乘法个数大于7的情况，可以直接搜索，会比 meet in middle 快。 std 0.55s, 好像时限开大了被暴力过了。 ### 1006 首先我们考虑每对点，对答案计算贡献。一对点 $i, j$ 对答案有贡献，当且仅当 $a_i=a_j$ 并且 $i$ 到 $j$ 之间的最大值和最小值都在 $l,r$ 之间。 对于每个数，如果出现了不超过 $B$ 次，那么我们可以把所有这样的点对求出来，一共不会超过 $O(nB)$ 对，区间内的最大值和最小值都可以用 $O(1)$ 的 RMQ 解决，也可以在求出每对相邻点区间内的最大值和最小值之后进行递推，这样一共只需要查 $O(n)$ 次 RMQ，用 $O(\log n)$ 也可以。把这些点对都拿出来之后，容易发现是个二维数点问题，可以通过扫描线解决。注意这里如果用树状数组做，时间复杂度可能会多一个 $\log$。但是修改操作比询问操作多很多，所以可以用修改 $O(1)$，询问 $O(\sqrt{n})$ 的分块做法解决。这部分的时间复杂度是 $O(nB+m\sqrt{n})$ 的。 如果出现次数超过了 $B$ 次，我们考虑每种数字单独解决。假设这个数字出现了 $k$ 次，那么这个数字每次出现的段里的最大值和最小值，会把值域划分成 $O(k)$ 段。如果询问对应的 $l,r$ 在值域中是同一段，那么答案也是一样的。所以我们可以把询问离散化，离散化之后使用莫队算法解决。这里在莫队算法的时候需要维护连续段，我们可以用不删除莫队+链表，就能在 $O(1)$ 的额外代价完成转移。时间复杂度是 $O(k\sqrt{m}+m)$ 的。所以后一半的时间复杂度是 $O(n\sqrt{m}+nm/B)$ 的。 取 $B=\sqrt{m}$，总的时间复杂度是 $O(n\sqrt{m}+m\sqrt{n})$。注意到后半部分的时间复杂度来自于求和的分块，我们可以把求和的结构改成 $t$ 层，每层 $n^{1/t}$。后半部分可以被改进到 $O(mn^{1/t})$。

# 数字游戏 存在至少一种方案，当且仅当 $min \le ave \le max$ 并且 $min * (n-1)+max \le ave * n \le min + max * (n - 1)$。 https://paste.ubuntu.com/p/NMXwPBWqBF/ # 网格路径 因为第一步只能从 $(1,1)$ 走到 $(1, 2)$ 或 $(2, 1)$，所以不相交路径最多只有两条。我们可以用如下方法构造两条路径： 1. 对于第一条路径，每次能向右走（走完以后可以顺利走到终点）就先向右走，不能向右走就向下走； 2. 对于第二条路径，每次能向下走（走完以后可以顺利走到终点）就先向下走，不能向下走就向右走； 接下来判断一下这两条路径是否存在以及是否相交就可以啦！ https://paste.ubuntu.com/p/b76XRkk593/ # 虫族基地 分如下几种情况考虑： 1. $(1, 1)$ 被第一个虫族基地占领了； 2. $(n, m)$ 被第二个虫族基地占领了； 3. 1 个虫族基地扩张，占领了完整的一列； 4. 2 个虫族基地扩张，并且领地切断了所有 $(1, 1)$ 到 $(n, m)$ 的路径； 在这些代价中取最小值即可。 https://paste.ubuntu.com/p/HQrq6x6595/ # 环上游走 暴力 dfs就可以过啦（如果当前走到的格子之前没走到过，就继续走，否则就回溯）！ https://paste.ubuntu.com/p/KTPdKn6rCH/ # 怀旧游戏 用 $f[i][j][k][l]$ 表示先手手上的数字是 $i, j$，后手手上的数字是 $k, l$ 时，先手的胜负情况。初始先手必败的情况比较好处理（$i$ 或 $j$ 是 0，意味着先手已经输了），接着反向 bfs，对于一个状态，如果它存在一个先手必败的后续状态，则这个状态先手必胜；如果它所有的后续状态都是先手必胜的，则这个状态先手必败。 对于无法确定胜负的状态，都是平局。 https://paste.ubuntu.com/p/M9KJzDCBZy/ # 消消乐 先处理完所有的终止状态（填满 8 个格子的不可以消除的状态），这些状态最后的期望得分都是 0。对于每个消完以后的状态 $x$（从初始的 8 个格子开始消，在新方块出现前的状态），我们可以枚举新方块的颜色情况，同时也知道了每种情况下消完以后的状态 $y$ 是啥样，以及得到了多少分，同时我们也知道从 $x$ 变成 $y$ 的概率，我们把期望方程列出来，高斯消元即可。 https://paste.ubuntu.com/p/XtKPn9mwVC/ # 二叉树 用 $f[i][j]$ 表示以 $i$ 为根的子树，这棵子树进出的点的数目为 $j$ 时（$j$ 可正可负，表示点是净移入还是净移出）在子树 $i$ 中花费的最小代价。对于每个 $i$，由于它只能有 2 个儿子，所以我们需要再做一次背包来计算 $f$。 https://paste.ubuntu.com/p/6z8VTF78rF/ # 数据结构 将区间视为平面上的点，如果一种颜色在区间内出现至少一次，需要考虑取答案对应的区间为： 1. 区间内相邻两次出现之间。 2. 区间左端点到区间内第一次出现。 3. 区间内最后一次出现到区间右端点。 可以用扫描线加线段树解决。 https://paste.ubuntu.com/p/M2bmSqysgW/

## 1001 发现 $2$ 次以后 $a,b$ 会变成 $2a,2b$ ，所以答案在 $k$ 为偶数时为 $a2^{\frac k2},b2^{\frac k2}$ ，$k$ 为奇数时为 $a2^{\frac {k-1}2}+b2^{\frac{k-1}2},a2^{\frac {k-1}2}-b2^{\frac{k-1}2}$ ，快速幂计算即可。 ## 1002 将 $a$ 数组排序后，贪心选取 $b$ 的值，每次选择大于上一个数的最小的数即可，如果不能选则这个数无法对答案进行贡献。时间复杂度 $O(Tn\log n)$ 。 ## 1003 发现除了起点和终点，剩下所有点周围的边都会被恰经过偶数次，所以这些点初始连向了偶数条白边。考虑由白边连接形成的图，每个连通块中度数为奇数的点一定为偶数个。所以起点所在连通块最多有两个点度数为奇数，且包含起点，不包含起点的连通块不能有点度数为奇数。所以每个包含白边的连通块都可以一笔画，每条白边都恰经过一次且不会经过黑边。答案即为 白边个数 $+2($ 包含白边或包含起点的连通块个数 $-1)$ 。 ## 1004 如果总和小于等于 $0$ ，那么如果在前两轮没有到达 $m$ 则永远无法到达 $m$ 。 如果总和大于 $0$ ，那么在第一轮过后，就不会再出现 $x<0$ 的情况了。从第一轮的前缀最小值开始，每操作 $n$ 次就会让 $x$ 加上总和，直接计算出两次前缀最小值之间的前缀最大值，计算什么时候最早到达 $m$ 即可。 ## 1005 交换 $3n$ 次之后排列的环的个数或不动点个数会远大于交换 $7n$ 次之后排列环的个数或不动点个数，直接判断大小即可。 ## 1006 考虑那个到 $S$ 中所有点距离互不相同的点，设直径长度为 $d$ ，则最多有 $d+1$ 种距离，所以 $|S|\leq d+1$ 。取直径即可取到 $d+1$ ，所以 $|S|$ 的最大值即为 $d+1$ 。 考虑枚举那个到 $S$ 中所有点距离互不相同的点，则对于这个点的方案数为 $\prod\limits_{x=0}^d$ 以这个点为根深度为 $x$ 的点的个数。发现如果存在两个直径端点 $x,y$ 且 $x$ 到 $y$ 的链都被选了，那么这个方案会被恰好算 $2$ 遍，剩下的只会被算 $1$ 遍，容斥减掉这种方案的个数即可。 ## 1007 考虑贪心，对于一个子树，维护这个子树里面答案的最小值和在这个子树根的人最多还能走几步。合并子树的时候直接将答案相加，并将在两个子树根的人贪心合并即可。 ## 1008 从小往大填数。需要对每种不同的数进行容斥，考虑求出 $f(i,a,b)$ 表示当前用了 $i$ 个不同的数，填了 $a+b$ 个数，并且只有右边 $b$ 个数旁边的 $b+1$ 个空位可以继续填更大的数字。对于一个 $f(i,a,b)$ ，考虑填第 $i+1$ 种数。 1. 如果可以随便填，则可以枚举填的数个数 $x$ ，乘上 $b+x\choose x$ 转移至 $f(i+1,a,b+x)$ 。 2. 但此时需要减去存在 $i<j$ 满足 $\max\limits_{k=1}^i a_k=\min\limits_{k=j}^na_k$ 且为第 $i+1$ 种数的情况。这种情况即为第 $i+1$ 种数出现了 $\geq 2$ 次且在最后一个空位填了这种数。所以可以枚举第一次出现位置和填的数个数，乘上 $b-k+x\choose x$ 转移至 $f(i+1,a+k+1,b-k+x+1)$ 。 直接暴力 $dp$ 求出所有 $f(i,a,b)$ ，再求出 $g(n,i)$ 表示填 $n$ 个数用了 $i$ 种不同的数的方案数。查询时直接枚举出现了多少种不同的数字，可以做到时间复杂度 $O(n^5+Tn)$ 。 考虑优化这个做法，维护出 $f_i(x,y)=\sum\limits_a\sum\limits_b y^a\frac{x^b}{b!}$ ，可以证明 $f_i(x,y)$ 可以写成 $\sum\limits_a\sum\limits_b c_{a,b}y^re^{sx}$ 的形式，有 $f_0(x,y)=1$ ，对每一个 $y^re^{sx}$ 项，考虑转移方式。 1. 第一种转移即为变成 $y^re^{sx}\times(e^x-1)$ 。 2. 对于第二种转移，依次考虑所有操作： 1. 枚举第一个数出现位置即为让 $a\leftarrow a+k+1,b\leftarrow b-k$ ，即乘上 $y^{k+1}$ 后对 $x$ 求 $k$ 次导数，对 $k$ 求和后变为 $\frac{y^{r+1}}{1-sy}e^{sx}$ 。 2. 在后面中任意放若干个数即为乘上 $e^x$ ，变为 $\frac{y^{r+1}}{1-sy}e^{(s+1)x}$ 。 3. 在最后放上一个数即为对 $x$ 积分再调整常数项，变为 $\frac{y^{r+1}}{1-sy}\frac 1{s+1}(e^{(s+1)x}-1)$ 。 对于一个 $y^re^{sx}$ ，其对答案的贡献为 $[y^n]\frac{y^r}{1-sy}$ 。 对于每一个 $i$ ，以上操作都可以在 $O(n^2)$ 内求出，总时间复杂度为 $O(n^3)$ ，可以通过此题。

## 1001 如果不考虑附魔，我们建立一个 $n \times n$ 的矩阵，其中 $a_{ij}$ 表示一步从 $i$ 到 $j$ 的概率（度数的逆元）。求出这个矩阵的 $k$ 次方为矩阵 $b$， $b_{1n}$ 即为答案。 若考虑附魔，我们将每个点拆成两个点：有附魔的和没附魔的。 对于每座普通桥，分别在有附魔的两个点和没附魔的两个点间连边。对于每座附魔桥，分别在对应的一个有附魔一个没附魔的点间连边。 最后用上文方法求出 $1$ 号普通点和 $n$ 号附魔点之间的概率即可。 单组数据时间复杂度 $O(n^3\log t)$。 ## 1002 &#65279;枚举含有 $0$ 的列可得 $q_n = \sum\limits_{k=0}^n \binom nk (2c)^k \binom{2n-k}{n-k}$ 观察得到 $q_n = [x^n] (1+2cx)^n (1-x)^{-n-1}$ 考虑逆用另类拉格朗日反演，则 $\begin{aligned} [x^n] Q(x) &= [x^n] (1+2cx)^n (1-x)^{-n-1} \\ &= [x^n] \frac1{1+2cx} \left(\frac{x}{x\frac{1-x}{1+2cx}}\right)^{n+1} \\ &= [x^n] \frac{1+2cx}{1-2x-2cx^2} \cdot \frac{1-2x-2cx^2}{(1+2cx)^2} \cdot \left(\frac{x}{x\frac{1-x}{1+2cx}}\right)^{n+1} \end{aligned}$ 因此，令 $G = x\frac{1-x}{1+2cx}$，$F$ 为 $G$ 的复合逆，则 $Q = \frac{1+2cF}{1-2F-2cF^2}$。 由 $G(F)=x$ 即 $F^2+(2cx-1)F+x=0$ 可以解出 $F = \frac{ 1 - 2 c x - \sqrt{1 - 4 (1 + c) x + 4 c^2 x^2} }2$ 代入可得 $Q = (4c^2x^2-4(c+1)x+1)^{-1/2}$ 令 $u = 4c^2x^2-4(c+1)x+1$，则 $2Q'u = - Q u'$ 可以 $O(n)$ 递推 $Q$ 的系数。 单组数据时间复杂度 $O(n)$。 ## 1003 考虑 DP，$f[i][j]$ 表示前 $i$ 个操作后，坏的电脑在 $j$ 的最小代价。 假设第 $i$ 次交换为 $u_i,v_i$，则 $f[i][u_i]=min(f[i-1][v_i],f[i-1][u_i]+1)$，$f[i][v_i]=min(f[i-1][u_i],f[i-1][v_i]+1)$。 对于其他的位置，$f$ 不变。 则利用滚动数组滚掉第一维，DP 转移每次只用修改 $O(1)$ 个位置的 $f$。 单组数据时间复杂度 $O(m)$。 ## 1004 因为 $a\bmod c=b\bmod c$，所以一定有 $a-b$ 为 $c$ 的倍数，于是枚举 $a-b$ 的因数进行检查即可。 注意特判 $a=b$ 的情况，此时如果 $a=1$，则答案为 $-1$，否则答案为 $2,a$。 单组数据时间复杂度 $O(\sqrt{\max(a,b)})$。 ## 1005 稍加推导后可得出一个结论： 当 $1 \lt +1 \lt y$ 时，$a_i=a_{i+1}+\dfrac{1}{n-i}$。 一波处理可以把原问题等价成一个满足 $x\le y$ 且 $y \times 2 \lt n$ 的问题。 设 $S=\sum\limits_{i=1}^{n-y}a_i$， 由前面的结论可以得到所有 $a$ 与 $a_{y-1}$ 之间的关系，并用 $a_{y-1}$ 表示出 $S$， 容易得到 $a_{y-1}=\dfrac{\sum\limits_{i=y}^{n}a_i}{n-y+1}+1=\dfrac{S}{n-y+1}+1$， $S=(n-y+1)(a_{y-1}-1)$， 结合之前用 $a_{y-1}$ 表示出的 $S$，就有了 $2$ 条方程，代入 $S=(n-y+1)(a_{y-1}-1)$ 后变为一元一次方程，一波操作后解得： $a_{y-1}=n-y+1+\sum\limits_{i=y}^{n-1}\sum\limits_{j=1}^i\dfrac{1}{j}-(n-y)\times\sum\limits_{i=1}^{n-y+1}\dfrac{1}{i}$ 通过 $a_{y-1}$ 可求得： $a_x=n-y+1+\sum\limits_{i=y}^{n-1}\sum\limits_{j=1}^i\dfrac{1}{j}-(n-y+1)\times\sum\limits_{i=1}^{n-y+1}\frac{1}{i}+\sum\limits_{i=1}^{n-x}\frac{1}{i}$ 在 $O(n)$ 预处理后每次询问可以做到 $O(1)$，总时间复杂度为 $O(n+T)$。 ## 1006 我们考虑维护最左边两个 $0$ 的位置，设其依次为 $a,b$。 若查询时，将 $a$ 设为了 $1$，则答案为 $b$，否则答案为 $a$。 修改时，若修改了 $a$，则令 $a=b$，之后 $b$ 一直递增，直到找到下一个 $0$。 若修改了 $b$，则 $b$ 之后一直递增，直到找到下一个 $0$。 这样整个序列最多被扫过 $2$ 次，总复杂度为 $O(n)$。 ## 1007 首先不难想到对每个 $m$，考虑将 $s$ 个儿子各自安排给 $m$ 个根的方案数；再考虑将剩下的 $n-m$ 个点组合成 $s$ 棵有根树的森林的方案数。 先考虑内层，由经典的 Prufer 序列立刻可知方案数就是 $\binom{n-m-1}{s-1} (n-m)^{n-m-s}$ 再考虑外层。显然这就是 $\left[\frac{x^s}{s!}\right] \left(\sum\limits_{i=0}^k \frac{x^i}{i!} \right)^m$ 设 $F = \sum\limits_{i=1}^k \frac{x^i}{i!}$ 则我们需要计算 $[x^s] \frac1{1-u(1+F)}$ 设 $G = F^{<-1>}$ 即 $F$ 的复合逆，根据拉格朗日反演可得答案为 $\frac1s [x^{s-1}] \frac{u}{(1-u(1+x))^2} \left(\frac xG\right)^s$ 若计算出 $G$，则容易从中提取所有 $u^m$ 的系数。 接下来叙述如何求出 $G$。 考虑 $F$ 显然满足 ODE $F = F' + \frac{x^k}{k!} - 1$ 代入 $x = G$ 得 $x = \frac1{G'} + \frac{G^k}{k!} - 1$ 整理得 $G' = \frac{k!}{k(1+x)-G^k}$ 解如此的一阶 ODE 可以使用牛顿迭代做到 $O(n \log n)$。 也可以转化为半在线卷积，做到 $O(n \log^2 n)$ 或 $O\left(\frac{n \log^2 n}{\log \log n}\right)$。 ## 1008 直接按题意模拟，每次都会死一个人，所以一定停机。 单组数据时间复杂度 $O(Tn^2)$。

### A 不难发现Alice的命中次数固定是$m$，也就是回复的生命值是$m$。只需要计算Bob对Alice造成的伤害即可。接下来就是简单的计算，容易发现除了第一次，以后每次都是差不多的，也就是Alice命中之后，由Bob先进行攻击，然后轮流攻击，直到Alice下次命中为止，这是一个简单的等比数列求和。 ### B 可以证明，最优操作方法一定是先把某个后缀改成全都是$1$，然后选择加一操作，然后接着直接改。于是可以枚举我们操作了哪个后缀，然后解决。 ### C 首先最小等价于每个区间找第$l+1-k$小，然后使得和最小，和最大基本等价，所以我们考虑最大。 最优方案中，假设$l=8, k=3$，那么一定会这么填000001110000011100000111...从大到小依次给这些位置$1$的位置填上数字。 证明大概可以考虑如果我们放了前$a$大的，使得尽量多第$k$大的大于等于这个数的尽量多，那么就等价于放$a$个$1$，使得不小于$k$个$1$的区间尽量多。 ### D 考虑$dp$，求出每个点的值，那么一个点有两种情况，一种是选两个儿子，然后不停地在这两个之间切换，一种是所有操作都在同一个儿子里面，其他的都不优。因为如果选两个儿子不停地切换，就相当于$dp_u=(dp_{s_1}+dp_{s_2})/2+1$，这个点本身每次access都会被切换到。感觉如果我们只选择一个比例去在两个儿子之间切换不太优，因为看起来像是个线性函数，所以要么均匀切换，要么不换。 所以就是求出两个儿子最大值，然后直接dp一下，注意这里的dp需要高精度维护，可以做到$O(n\log n/w)$，但是没必要，这里使用$O(n^2/w)$就可以解决。 ### E 考虑一个二维的$dp$模型，考虑连续两轮，如果两个人都miss了，那么没有意义，所以可以看做$\frac{p(1-q)}{1-(1-p)(1-q)}$的概率转移向$n-1,m$，$\frac{q(1-p)}{1-(1-p)(1-q)}$转移向$n,m-1$，剩下的概率转移向$n-1,m-1$。记上面三步走分别为$A, B, C$。那么Bob死亡的话，一定是走到了$x,1$的情况，然后被Alice一下打死。这样我们就知道B和C的总步数。我们首先将BC当作一个整体，个数是固定的，然后可以和A插板求出，走多少步A，那么A和BC这样的序列方案数。然后我们枚举C的步数，那么可以知道A至多可以走几步，可以使用前缀和算出答案，时间复杂度$O(n+m)$。 ### F 考虑离线，每个点维护一个关于时间的$g$值数组，每个点可以看成从父亲继承下来一个数组，然后看这个点改了哪些值，就相当于是对这些区间max上了一个值。所以本质上是一个需要撤销的segment beats问题，直接做是不行的，所以可以分块解决。