杭州中超联赛战前培训（上）
天命之路
·
·
个人记录
2022.11.29
今天前两题其实都不算难，但因为打着打着想下班了，就只写了 T1 和 T3 的一点分，没有认真思考 T2。
T1 是个简单题：
给出 m 条限制 (x,y)，要求计数长度为 n 的排列 p_1,p_2,\dots,p_n 使得对于每个限制 (x,y) 均有 p_x = y 或 p_y = x。\Theta(n \log n)
放在置换环上考虑，一个限制相当于一条无向边。
显然有点度数大于 2 就无解。有一个自环连接其他点也无解。
否则每个联通块有四种情况：
- 自环，舍去
- 孤立点，需要被插入置换环
- 一个整环，显然它不能对其他的点有影响，故将最后的答案 \times 2 即可
- 一条链，将其定向之后同孤立点没什么区别。
唯一的例外是一个长度为 2 的链单独成环的时候，对这条链定向没有意义。
设有 s_1 条长度 \ge 3 的链，s_2 条长度为 2 的链，s_3 个孤立点。
则枚举恰好有 i 个长度为 2 的链单独成环，则剩下的 s_2 - i 个都不能单独成环。
内层相当于一个错排，一共有 s_1+s_2+s_3-i 个点，其中 1 到 s_2 - i 不能单独成环。可以容斥。
d
把式子写在一起推一推可以得出一个卷积做法，这里就不细讲了。（考场做法，但因为找环的 dfs 写错了挂成 20)
考虑先假设所有长度为 2 的链都有 2 的系数，那么一个长度为 2 的链单独成环就有 \dfrac{1}{2} 的系数。
大家应该还记得，容斥是使用二项式定理证明的。
我们容斥“一个东西不出现的方案数“，实际上是在说它的权值是 0,此时容斥系数是 -1。
现在出现一个东西的权是 \dfrac{1}{2}，那容斥系数就是 \dfrac{1}{2} - 1 = -\dfrac{1}{2}。
所以直接钦定有 i 个二元链成自环，容斥系数就是 (\dfrac{-1}{2})^i。
T2 是个拆贡献线段树题，到时候补。
T3 是个套路题。
输入 n 个字符串 s_1,s_2,\dots,s_n。
有一个初始为空的字符串 T，每次在后面等概率加入一个小写字母，当所有 s_i 均在 T 中出现至少一次时，停止加入字符。
问 T 的期望长度。
1 \le n \le 15,1 \le \sum |s_i| \le 10^5
设 X_i 表示 s_i 最早出现的时间。
所求即为 E(\max(X_i))。
这就是 [SDOI2017] 硬币游戏，我们把它重新推一遍。
我们使用暴力的 $PGF$ 推导。
设 $F_i(x)$ 表示 $s_i$ 的 $PGF$，即 $[x^t]F_i(x)$ 表示 $X_i = t$ 的概率。
设 $G(x)$ 表示一直没有出现任何一个串的 $PGF$，即 $[x^t]G(x)$ 表示到了时间 $t$ 还没有一个串出现的概率。
首先 $G(1)$ ，即所有时间都没出现的概率之和，其实就是第一次有串出现的时间的期望，可以参考等式 $E(X) = \sum_{i \ge 1} iP(X = i) = \sum_{i \ge 0} P(X > i)$ 进行理解。
考虑列出 $F_i$ 与 $G$ 的关系式。
首先有
$$ \sum_{i=1}^n F_i(x) + G(x) = xG(x) + 1$$
具体地，就是考虑 $g_i = f_{i +1} + g_{i+1}$，即当前没结束，下一步可能结束或没结束。
再者，对于每个 $s_i$，不管当前的 $T$ 是什么，只要往后拼一个 $s_i$，必然会结束。
唯一的问题是，我们可能还没有把一个 $s_i$ 拼完，事情就结束了。
也就是说，我们可能拼了一个 $s_i$ 的前缀，然后跟原来 $T$ 的某个后缀形成了一个 $s_j$，就贡献到了“直接往后拼一个 $s_i$" 的方案当中去。
设 $|s_i| = L$，则对于每个 $i$，有方程：
$$
G(x)(\dfrac{1}{|\Sigma|})^mx^m = \sum_{j=1}^n\sum_{k=1} [s_i[1,\dots,k] =s_j[|s_j|-k+1,\dots,|s_j|]]F_j(x) x^{m - k}(\dfrac{1}{|\Sigma|})^{m-k}
$$
其中 $\Sigma$ 是字符集，这里$|\Sigma| = 26$。
将 $x = 1$ 代入上面 $n + 1$ 个式子，即可得到关于 $F_i(1)$ 和 $G(1)$ 的 $n + 1$ 个方程，高斯消元解方程即可。
注意第二个式子的系数需要在一开始就处理好，因为我们要解 $2^n$ 遍方程。
时间复杂度为 $\Theta(2^nn^3 + n\sum |s_i|)$ 或 $\Theta(2^nn^3 + n^2 \sum|s_i|)$ ，取决于预处理复杂度。
## 2022.11.30
得分：100+100+30=230,大众分。
写一下第三题。
给出一个 $n$ 个点的无向环，第 $i$ 个点同第 $(i + 1) \bmod n$ 个点之间，有一条权值为 $w_i$ 的无向边。（$0 \le i \le n - 1$）。
再给出 $m$ 条无向边 $(u_i,v_i,w_i)$ 。
特殊条件：如果把这张图画在一个平面上，这 $m$ 条无向边不会在端点以外的地方相交，即开区间 $(u_i,v_i)$ 和 $(u_j,v_j)$ $(i \ne j)$ 要么互相包含，要么无交。
设 $\operatorname{dis}(i,j)$ 表示 $i$ 到 $j$ 的最短路。
求 $\sum_{i=1}^n\sum_{j=i+1}^n \operatorname{dis}(i,j)$。
$n,m \le 2 \times 10^5$。
在平面图上的点对相关问题，考虑分治。
取出一条不在环上的边 $(x,y)$ ，整张图就被分成了两个部分，设两个部分的点集为 $L,R$。
考虑对于 $u \in L,v \in R$ 统计贡献。
因为 $u$ 到 $v$ 的最短路必定经过 $x,y$ 中的至少一个，故 $dis(u,v) = \min(dis(u,x)+dis(v,x),dis(u,y)+dis(v,y))
我们要求 $\min$，考虑把贡献分类，即考虑什么时候 $dis(u,x) + dis(v,x) \le dis(u,y)+dis(v,y)$。
移项变成 $dis(u,x) - dis(u,y) \le dis(v,y) - dis(v,x)
左边就只和 u 有关，右边就只和 v 有关。
可以把 dis(u,x) - dis(u,y)(u \in L) 和 dis(v,y) - dis(v,x) (v \in R) 放入同一个数组中进行排序。然后从前往后扫描就可统计贡献。
考虑如何向下递归。
直接向下递归是不行的，因为对于 u,v \in L，u 到 v 的最短路仍然可能经过 R 中的点。
但我们注意到，这仍然会经过 x 和 y。
所以我们向下递归时，把 x 到 y 的权值赋为 dis(x,y)，就包含了这种情况。
但是，直接这样递归的复杂度是错的。
因为我们的分治基于题目给出的 m 条边，如果这 m 条边分出来的两半都不太均匀，那么复杂度就会上去。
一个策略是把这 m 条边补成一个三角剖分（补上的边的边权设为 \infty)，然后每次找到使 \max(|L|,|R|) 最小的 (x,y)，递归下去，复杂度就是对的。
证明的话，把环上的点均匀地放到一个圆上，找到一个包含圆心的三角形 ，这个三角形会把原图的点分成三个部分 A,B,C，有 |A|+|B|+|C| = n + 3。
显然会有 \max(|A|,|B|,|C|) \ge \frac{n}{3}+1，因为三角形包含圆心，也会有 \max(|A|,|B|,|C|) \le \frac{n}{2}+1。
所以我们找 L,R 的时候，总能找到一对 L,R 满足 \frac{n}{3}+1 \le |L| \le \frac{n}{2}+1，所以你能找到一对 L,R 满足 \max(|L|,|R|) \le \frac{2}{3}n
最坏的情况下，T(n) = T(\frac{1}{3}n) + T(\frac{2}{3}n) + O(n \log n)。可以分析出总复杂度为 \Theta(n \log ^2 n)。
至于如何把现有的 m 条边补成一个三角剖分。考虑找出一个度数为 0 的点（即不与这 m 条边的任何一条相连)，设其为 x，然后考察其左边和右边的点 l,r，如果 l 与 r 之间没有连边，就连上。
这样，l,r,x 就会形成一个三角形，且贴在环的边上，我们大可以把点 x 删掉，把 l,r 之间的的那条非环边变为新的环边（即将 l,r 的度数都减 1），然后重复上述过程。可以类似拓扑排序，用队列维护当前度数为 0 的点。并用双向链表维护删点即可。
代码如下：
for(int i = 0;i < m;i++)
{
E[e[i].x].insert(e[i].y),
E[e[i].y].insert(e[i].x);
++deg[e[i].x];++deg[e[i].y];
}
queue<int> Q;
for(int i = 0;i < n;i++)
if(!deg[i]) Q.push(i);
for(int i = 0;i < n;i++)
L[i] = i - 1,R[i] = i + 1;
L[0] = n - 1;R[n - 1] = 0;
while(!Q.empty())
{
int x = Q.front();Q.pop();
int lef = L[x],righ = R[x];
R[lef] = righ;L[righ] = lef;
if(lef > righ) swap(lef,righ);
if(lef == righ || (lef == 0 && righ == n - 1) || righ - lef == 1) continue;
if(!E[lef].count(righ))
{
E[lef].insert(righ);E[righ].insert(lef);
e.push_back(Edge(lef,righ,inf));
}
else
{
if((--deg[lef]) == 0) Q.push(lef);
if((--deg[righ]) == 0) Q.push(righ);
}
}
2022.12.1
得分：0+85+0，T2 因为有一个地方写挂痛失 15 分，差点就签到成功了。
11.30 的 T3 是赛时写完 T2 之后改的。
2022.12.2-2022.12.6
模拟赛没有什么可改的题，但讲课的课件还是有很多不错的题的。
会随缘更新一些学到的东西。
1. 多项式点值平移
对于一个 n 次多项式 f，给出 f(0),f(1),\dots,f(n) ，现在需要求出 f(m),f(m+1),\dots,f(m+n)。对 998244353 取模。
考察拉格朗日插值的式子：
$$
\begin{aligned}
f(m + t) = \sum_{i=0}^{n}f(i)\prod_{j != i}\dfrac{m + t - j}{i-j} \\
= \sum_{i=0}^{n} \dfrac{f(i)(-1)^{n-i}}{i!(n-i)!} \prod_{j != i} (m+t-j)! \\
= \dfrac{(m+t)!}{(m-n+t-1)!}\sum_{i=0}^n \dfrac{f(i)(-1)^{n-i}}{i!(n-i)!} \dfrac{1}{m+t-i} \\
\end{aligned}
$$
后半部分显然是个卷积的形式，唯一的不足是后面的求和上界是 $n$ 而不是 $t$。
因为 $t$ 可能小于 $n$,我们要化成卷积的形式，最方便的当然是取某个序列的第 $n + t$ 项作为答案，虽然我们还不知道这个序列是什么。
进一步地，我们把 $\dfrac{1}{m+i}$ 这个序列也类似地平移 $n$ 位,具体地，我们设
$$
\begin{aligned}
A_i = \dfrac{f(i)(-1)^{n-i}}{i!(n-i)!} (i \in [0,n]) \\
B_i = \dfrac{1}{m-n+i} (i \in [0,2n]) \\
\end{aligned}
$$
然后令 $C = A * B$，取 $C_{n+t}$ 就是 $f(m+t)$ 的后面那个 $\sum$。
一遍卷积即可，时间复杂度 $\Theta(n \log n)$。
#### 2. P5469 机器人
从初三的暑假到高一上学期，计数水平确乎是有提升的，也有可能是思路变得更加敏捷，总而言之，看懂机器人了。
题意：
从左到右有一排长度为 $n$ 的柱子，设柱子 $i$ 的高度为 $h_i$。有两种机器人，`P` 型机器人和 `Q` 型机器人。
`P` 型机器人从某个柱子出发，会一直向左走，直到走到尽头或者下一个柱子的高度**大于**起点柱子。
`Q` 型机器人从某个柱子出发，会一直向右走，直到走到尽头或者下一个柱子的高度**大于等于**起点柱子。
如果 $\forall s \in [1,n]$，把两个机器人放在 $s$ 处，让他们走，他们走过的格子数量之差的绝对值不超过 $2$。那么这个 $h_i$ 序列就被称作合法的。
现在限定 $h_i \in [A_i,B_i]$（$A,B$ 给定）计数有多少个合法的 $h_i$。对 $10^9 + 7$ 取模。
$n \le 300,1 \le A_i \le B_i \le 10^9$。
题目中的机器人在走到第一个大于/大于等于起点的位置就会停止，我们不妨考虑，如果把起点设在整个数列最靠右的最大值会发生什么。设这个位置为 $t$。
显然，`P` 型机器人会一直向左，`Q` 型机器人会一直向右，直到走到端点，而在 $t$ 的左边或右边，机器人无论怎么走都无法跨过 $t$。
所以我们借助这个最大值，把一个区间拆成了两个子区间，和一个断点的决策。**（这是十分重要的思想，通过特殊点的表现来拆分问题）**
于是考虑设计一个 $dp[l][r]$ 表示区间 $[l,r]$ 的答案，转移枚举最大值的位置，因为其与两边距离之差不超过 $2$，有效的转移不多，在 $n \le 300$ 时只有 $2518$ 个有效区间。
但枚举最大值本身还会带来限制，子区间的最大值必须**小于或小于等于**枚举的端点
所以我们还要记录一维 $v$ 表示当前转区间的最大值，状态就是 $dp[l][r][v]$，设其前缀和为 $sum[l][r][v] = \sum_{i=1}^v dp[l][r][v]
那么转移就是
\begin{aligned}
dp[l][r][v] &= \sum_{\text{$t$ is vaild} } ((\sum_{i=1}^{v}dp[l][t - 1][i]) \times (\sum_{i=1}^{v-1} dp[t + 1][r][i]))[a_t \le v \le b_t] \\
&= \sum_{\text{$t$ is vaild}} sum[l][t - 1][v] \times sum[t + 1][r][v - 1][a_t \le v \le b_t]
\end{aligned}
但 v 有可能很大，如果直接实现这个东西，显然是无法满分的。
我们思考 a = 1,b = 10^9 那档部分分，现在相当于 v 的取值不受限制。
考虑一个 l = r 的区间，它满足 dp[l][r][v] = 1，其前缀和满足 sum[l][r][v] = v
考虑一个 l + 1 = r 的区间，他就是如上的两个 sum 点乘的结果，显然是个二次函数。
归纳地，设 F_{l,r}(x) = sum[l][r][x] 是一个关于 x 的函数，我们可以证明这是个次数不超过 r - l + 1 次的多项式，对着 dp 方程考虑即可得证。
也就是说，我们只要算出了 sum[1][n][x] 在 x = 0,1,\dots,n 的取值，就能通过插值算法得出 sum[1][n][10^9]。
我们转而考虑正解，此时 a,b 不一样，哪怕是 i 固定，每个 v 都有可能可以被取或者不能被取，这取决于 a 和 b 的限制。
这意味着答案不再是个多项式。
但我们考虑把 a,b 按照数轴上离散化的方法处理。
那么对于两个特殊值 vals_i,vals_{i+1} 形成的区间 [vals_i,vals_{i+1}) 中的 v ，在 i 一定时决策都是一样的，要么取，要么不取，这样答案就是一个多项式，能不能取的决策无非是多乘一项，少乘一项的区别。
值得注意的是，我们在 [vals_i,vals_{i+1}) 的值域中考虑 "dp[l][r][v] 的前缀和" 时，它仍然是从 1 开始求和的，而非 vals_i，所以我们需要一个位置来保存在更小的值域区间内 dp[l][r][v] 的前缀和，这在代码里体现为 dp[l][r][0]。
3.P4654 [CEOI2017] Mousetrap
有题号就不放题意了。
虽然看着是个博弈题，但跟博弈其实关系不大，我们只需通过一定的方法，刻画这两个人在不同局面下的决策即可。
我们考虑把陷阱点作为根，那么老鼠就是要向上一直跳，然后跳到根。
容易发现，如果老鼠跳着跳着，转头向下，进入了某棵子树，那他就只能在某个叶子处等待收编，因为管理员不清理他就上不去，而且老鼠能动就必须要动。
所以，管理员大可以把他想堵的边都堵住了之后，再来把老鼠通往陷阱的路径清扫干净。
而老鼠进入子树再出来的代价只同他在哪棵子树有关。
故可以设 f[x] 表示老鼠进入了 x 子树后再把他赶出来的最小代价。
老鼠在点 x 时，他显然会走 f[y] 最大的儿子 y。
但管理员显然会堵上这个儿子，所以老鼠会走 f[y] 次大的儿子。
设 num_x 表示 x 的儿子个数，则
f[x] = \operatorname{2ndmax}_{y \in son(x)}(f[y]) + num_x
有 num_x - 1 个儿子要堵上，有 1 个儿子在最后要疏通，所以代价是 num_x。
但是，对于一次博弈，老鼠可以先向上跳一点，再一头扎进一棵子树。
但老鼠会钻进哪棵子树？
这个影响因素其实很多，并不是简单的把所有代价取 \max 就是最优解的。
我们考虑二分答案，设当前有 k 个可用操作。
那么假设你老鼠打算在 x 点，一头扎进某个子树 y。
设把 x 以上的路径的邻域全部堵住的代价是 sum[x]。
则对于 sum[x] + f[y] \le k 的子树，其实我们是不需要堵住他的，但大于则需要，这本身又会花费一个操作（从这个角度来看，答案确实需要二分，不能直接求，因为决策比想象中复杂）
另一方面，假设点 x 一共有 cnt 个 sum[x] + f[y] \gt k 的子树，那么在老鼠到达点 x 之前，这些树就要全部堵上。
把这两个条件判断之后，就可以充要地判定 k 次操作是否可以收编老鼠。
然后这题就做完了。
4.P4202 [NOI2008] 奥运物流
有题号就不放题意了。
先考虑如何计算 R(i)
如果原图是一个环，那么 有 R(i) = C_i + kR(i \bmod n + 1)
手动消元可得 R(1) = \dfrac{\sum_{i}C_i k^{i-1}}{1-k^n}。
另一方面，如果原图是个内向树，容易推出 R(1) = \sum_i C_i k^{dep(i)}
综合以上两点可以得到 R(1) = \dfrac{\sum_i C_i k^{dis(i \to 1)}}{1-k^{len}}
具体地，可以先把环外的内向树都递推上来，再放到环上考虑，即可证明这一点。
显然，我们改一个点的后继，最优的方法是直接改到 1 号节点。
考察原来的式子，我们可以决定的是 dis(i \to 1) 和环长 len。
我们不妨枚举环长，那么此时的环就是可以确定的，就是 1 号点后面若干个点。
我们大可以把 1 号点的出边忽略，它对答案没有影响。
接下来变成内向树上的问题。
我们设 dp[u][m][d] 表示在 u 子树内，用了 m 次修改机会，点 u 的深度现在为 d 的最优答案。
树上背包转移即可。
5. CF1119F Niyaz and Small Degrees
有题号就不放题意了。
我们考虑单个答案怎么求。
容易想到设 f[x][0],f[x][1] 表示 x 与 fa[x] 之间的边割或不割。dp 时，先把这些状态的值都设成 \sum_{y} \min(f[y][1] + w,f[y][0]) ，但这个和式对应的方案不一定是合法的，也就是说，我们要把一些 dp[y][1] + w > dp[y][0] 的儿子 y ，由不割 (y,x) 强行变为割掉 (y,x) ，并将答案加上对应的增量。我们可以开个堆，来取出增量前若干小的儿子 y 做这个事情，这样就可以 \Theta(n^2 \log n) 完成这次树形 dp。
我们考虑，随着度数限制 D 的增大，问题的规模是在变小的，具体地，对于 deg[x] 已经不超过 D 的点 x，我们树形 dp 时其实没必要经过它，我们只关心它和它某个邻居之间的那条边要不要被割，我们可以把它当成一个孤立点，并把它的信息放到邻域上。
具体地，有如下代码：
inline void Destroy(int x)
{
for(auto it : G[x])
{
int y = it.first,w = it.second;
if(deg[y] <= D) break;
H[y].push(w);
}
}
接下来我们对度数大于等于 D 的点，做如上的树形 dp 即可。
事实上，这样的复杂度就是 \Theta(n \log n)。
具体地，可以考虑等式 \sum_{i=1}^n \sum_{D = 0}^{n - 1} [deg_i \gt D] = \sum_{i=1}^n deg_i = 2n-2。
在代码实现上，我们把所有邻居按度数从大到小排序，遍历到 \le D 的点就直接 break 而非 continue 。
在 dp 的时候，我们维护大根堆，当堆的大小超过限制时就把堆顶删去，这样可以时刻保证堆的大小不超过 deg[x] - D，此时我们的堆中会删除一些值，但删完之后，我们也必须把它加回来，因为这里面包含了一些孤立点的信息。
这些都是为了保证复杂度而需要注意的细节。