2022.11.29

今天前两题其实都不算难，但因为打着打着想下班了，就只写了 T1 和 T3 的一点分，没有认真思考 T2。

T1 是个简单题：

给出 条限制 ，要求计数长度为 的排列 使得对于每个限制 均有 或 。

放在置换环上考虑，一个限制相当于一条无向边。

显然有点度数大于 就无解。有一个自环连接其他点也无解。

否则每个联通块有四种情况：

1. 自环，舍去
2. 孤立点，需要被插入置换环
3. 一个整环，显然它不能对其他的点有影响，故将最后的答案 即可
4. 一条链，将其定向之后同孤立点没什么区别。

唯一的例外是一个长度为 的链单独成环的时候，对这条链定向没有意义。

设有 条长度 的链， 条长度为 的链， 个孤立点。

则枚举恰好有 个长度为 的链单独成环，则剩下的 个都不能单独成环。

内层相当于一个错排，一共有 个点，其中 到 不能单独成环。可以容斥。 d 把式子写在一起推一推可以得出一个卷积做法，这里就不细讲了。（考场做法，但因为找环的 dfs 写错了挂成 20)

考虑先假设所有长度为 的链都有 的系数，那么一个长度为 的链单独成环就有 的系数。

大家应该还记得，容斥是使用二项式定理证明的。

我们容斥“一个东西不出现的方案数“，实际上是在说它的权值是 0,此时容斥系数是 。

现在出现一个东西的权是 ，那容斥系数就是 。

所以直接钦定有 个二元链成自环，容斥系数就是 。

T2 是个拆贡献线段树题，到时候补。

T3 是个套路题。

输入 个字符串 。

有一个初始为空的字符串 ，每次在后面等概率加入一个小写字母，当所有 均在 中出现至少一次时，停止加入字符。

问 的期望长度。

设 表示 最早出现的时间。

所求即为 。

容斥一下，所求即为 。

这就是 [SDOI2017] 硬币游戏，我们把它重新推一遍。

我们使用暴力的 推导。

设 表示 的 ，即 表示 的概率。

设 表示一直没有出现任何一个串的 ，即 表示到了时间 还没有一个串出现的概率。

首先 ，即所有时间都没出现的概率之和，其实就是第一次有串出现的时间的期望，可以参考等式 进行理解。

考虑列出 与 的关系式。

首先有

具体地，就是考虑 ，即当前没结束，下一步可能结束或没结束。

再者，对于每个 ，不管当前的 是什么，只要往后拼一个 ，必然会结束。

唯一的问题是，我们可能还没有把一个 拼完，事情就结束了。

也就是说，我们可能拼了一个 的前缀，然后跟原来 的某个后缀形成了一个 ，就贡献到了“直接往后拼一个 " 的方案当中去。

设 ，则对于每个 ，有方程：

其中 是字符集，这里。

将 代入上面 个式子，即可得到关于 和 的 个方程，高斯消元解方程即可。

注意第二个式子的系数需要在一开始就处理好，因为我们要解 遍方程。

时间复杂度为 或 ，取决于预处理复杂度。 ## 2022.11.30

得分：100+100+30=230,大众分。

写一下第三题。

给出一个 个点的无向环，第 个点同第 个点之间，有一条权值为 的无向边。（）。

再给出 条无向边 。

特殊条件：如果把这张图画在一个平面上，这 条无向边不会在端点以外的地方相交，即开区间 和 要么互相包含，要么无交。

设 表示 到 的最短路。

求 。

。

在平面图上的点对相关问题，考虑分治。

取出一条不在环上的边 ，整张图就被分成了两个部分，设两个部分的点集为 。

考虑对于 统计贡献。

因为 到 的最短路必定经过 中的至少一个，故

和 可以用 Dijkstra 跑出来。

我们要求 ，考虑把贡献分类，即考虑什么时候 。

移项变成

左边就只和 有关，右边就只和 有关。

可以把 和 放入同一个数组中进行排序。然后从前往后扫描就可统计贡献。

考虑如何向下递归。

直接向下递归是不行的，因为对于 ， 到 的最短路仍然可能经过 中的点。

但我们注意到，这仍然会经过 和 。

所以我们向下递归时，把 到 的权值赋为 ，就包含了这种情况。

但是，直接这样递归的复杂度是错的。

因为我们的分治基于题目给出的 条边，如果这 条边分出来的两半都不太均匀，那么复杂度就会上去。

一个策略是把这 条边补成一个三角剖分（补上的边的边权设为 )，然后每次找到使 最小的 ，递归下去，复杂度就是对的。

证明的话，把环上的点均匀地放到一个圆上，找到一个包含圆心的三角形 ，这个三角形会把原图的点分成三个部分 ，有 。

显然会有 ，因为三角形包含圆心，也会有 。

所以我们找 的时候，总能找到一对 满足 ，所以你能找到一对 满足

最坏的情况下，。可以分析出总复杂度为 。

至于如何把现有的 条边补成一个三角剖分。考虑找出一个度数为 的点（即不与这 条边的任何一条相连)，设其为 ，然后考察其左边和右边的点 ，如果 与 之间没有连边，就连上。

这样， 就会形成一个三角形，且贴在环的边上，我们大可以把点 删掉，把 之间的的那条非环边变为新的环边（即将 的度数都减 ），然后重复上述过程。可以类似拓扑排序，用队列维护当前度数为 的点。并用双向链表维护删点即可。

代码如下：

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 因为有一个地方写挂痛失 分，差点就签到成功了。

11.30 的 T3 是赛时写完 T2 之后改的。

2022.12.2-2022.12.6

模拟赛没有什么可改的题，但讲课的课件还是有很多不错的题的。

会随缘更新一些学到的东西。

1. 多项式点值平移

对于一个 次多项式 ，给出 ，现在需要求出 。对 取模。

。

考察拉格朗日插值的式子：

后半部分显然是个卷积的形式，唯一的不足是后面的求和上界是 而不是 。

因为 可能小于 ,我们要化成卷积的形式，最方便的当然是取某个序列的第 项作为答案，虽然我们还不知道这个序列是什么。

进一步地，我们把 这个序列也类似地平移 位,具体地，我们设

$$

$$

然后令 ，取 就是 的后面那个 。

一遍卷积即可，时间复杂度 。

2. P5469 机器人

从初三的暑假到高一上学期，计数水平确乎是有提升的，也有可能是思路变得更加敏捷，总而言之，看懂机器人了。

题意：

从左到右有一排长度为 的柱子，设柱子 的高度为 。有两种机器人，P 型机器人和 Q 型机器人。

P 型机器人从某个柱子出发，会一直向左走，直到走到尽头或者下一个柱子的高度大于起点柱子。

Q 型机器人从某个柱子出发，会一直向右走，直到走到尽头或者下一个柱子的高度大于等于起点柱子。

如果 ，把两个机器人放在 处，让他们走，他们走过的格子数量之差的绝对值不超过 。那么这个 序列就被称作合法的。

现在限定 （ 给定）计数有多少个合法的 。对 取模。

。

题目中的机器人在走到第一个大于/大于等于起点的位置就会停止，我们不妨考虑，如果把起点设在整个数列最靠右的最大值会发生什么。设这个位置为 。

显然，P 型机器人会一直向左，Q 型机器人会一直向右，直到走到端点，而在 的左边或右边，机器人无论怎么走都无法跨过 。

所以我们借助这个最大值，把一个区间拆成了两个子区间，和一个断点的决策。（这是十分重要的思想，通过特殊点的表现来拆分问题）

于是考虑设计一个 表示区间 的答案，转移枚举最大值的位置，因为其与两边距离之差不超过 ，有效的转移不多，在 时只有 个有效区间。

但枚举最大值本身还会带来限制，子区间的最大值必须小于或小于等于枚举的端点

所以我们还要记录一维 表示当前转区间的最大值，状态就是 ，设其前缀和为

那么转移就是 但 有可能很大，如果直接实现这个东西，显然是无法满分的。

我们思考 那档部分分，现在相当于 的取值不受限制。

考虑一个 的区间，它满足 ，其前缀和满足

考虑一个 的区间，他就是如上的两个 点乘的结果，显然是个二次函数。

归纳地，设 是一个关于 的函数，我们可以证明这是个次数不超过 次的多项式，对着 方程考虑即可得证。

也就是说，我们只要算出了 在 的取值，就能通过插值算法得出 。

我们转而考虑正解，此时 不一样，哪怕是 固定，每个 都有可能可以被取或者不能被取，这取决于 和 的限制。

这意味着答案不再是个多项式。

但我们考虑把 按照数轴上离散化的方法处理。

那么对于两个特殊值 形成的区间 中的 ，在 一定时决策都是一样的，要么取，要么不取，这样答案就是一个多项式，能不能取的决策无非是多乘一项，少乘一项的区别。

值得注意的是，我们在 的值域中考虑 " 的前缀和" 时，它仍然是从 开始求和的，而非 ，所以我们需要一个位置来保存在更小的值域区间内 的前缀和，这在代码里体现为 。

3.P4654 [CEOI2017] Mousetrap

有题号就不放题意了。

虽然看着是个博弈题，但跟博弈其实关系不大，我们只需通过一定的方法，刻画这两个人在不同局面下的决策即可。

我们考虑把陷阱点作为根，那么老鼠就是要向上一直跳，然后跳到根。

容易发现，如果老鼠跳着跳着，转头向下，进入了某棵子树，那他就只能在某个叶子处等待收编，因为管理员不清理他就上不去，而且老鼠能动就必须要动。

所以，管理员大可以把他想堵的边都堵住了之后，再来把老鼠通往陷阱的路径清扫干净。

而老鼠进入子树再出来的代价只同他在哪棵子树有关。

故可以设 表示老鼠进入了 子树后再把他赶出来的最小代价。

老鼠在点 时，他显然会走 最大的儿子 。

但管理员显然会堵上这个儿子，所以老鼠会走 次大的儿子。

设 表示 的儿子个数，则 有 个儿子要堵上，有 个儿子在最后要疏通，所以代价是 。

但是，对于一次博弈，老鼠可以先向上跳一点，再一头扎进一棵子树。

但老鼠会钻进哪棵子树？

这个影响因素其实很多，并不是简单的把所有代价取 就是最优解的。

我们考虑二分答案，设当前有 个可用操作。

那么假设你老鼠打算在 点，一头扎进某个子树 。

设把 以上的路径的邻域全部堵住的代价是 。

则对于 的子树，其实我们是不需要堵住他的，但大于则需要，这本身又会花费一个操作（从这个角度来看，答案确实需要二分，不能直接求，因为决策比想象中复杂）

另一方面，假设点 一共有 个 的子树，那么在老鼠到达点 之前，这些树就要全部堵上。

把这两个条件判断之后，就可以充要地判定 次操作是否可以收编老鼠。

然后这题就做完了。

4.P4202 [NOI2008] 奥运物流

有题号就不放题意了。

先考虑如何计算

如果原图是一个环，那么 有

手动消元可得 。

另一方面，如果原图是个内向树，容易推出

综合以上两点可以得到

具体地，可以先把环外的内向树都递推上来，再放到环上考虑，即可证明这一点。

显然，我们改一个点的后继，最优的方法是直接改到 号节点。

考察原来的式子，我们可以决定的是 和环长 。

我们不妨枚举环长，那么此时的环就是可以确定的，就是 号点后面若干个点。

我们大可以把 号点的出边忽略，它对答案没有影响。

接下来变成内向树上的问题。

我们设 表示在 子树内，用了 次修改机会，点 的深度现在为 的最优答案。

树上背包转移即可。

5. CF1119F Niyaz and Small Degrees

有题号就不放题意了。

我们考虑单个答案怎么求。

容易想到设 表示 与 之间的边割或不割。dp 时，先把这些状态的值都设成 ，但这个和式对应的方案不一定是合法的，也就是说，我们要把一些 的儿子 ，由不割 强行变为割掉 ，并将答案加上对应的增量。我们可以开个堆，来取出增量前若干小的儿子 做这个事情，这样就可以 完成这次树形 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);
	}
}

接下来我们对度数大于等于 的点，做如上的树形 dp 即可。

事实上，这样的复杂度就是 。

具体地，可以考虑等式 。

在代码实现上，我们把所有邻居按度数从大到小排序，遍历到 的点就直接 break 而非 continue 。

在 dp 的时候，我们维护大根堆，当堆的大小超过限制时就把堆顶删去，这样可以时刻保证堆的大小不超过 ，此时我们的堆中会删除一些值，但删完之后，我们也必须把它加回来，因为这里面包含了一些孤立点的信息。

这些都是为了保证复杂度而需要注意的细节。