总结

冬月廿五，小寒。腊月就要来了。冬至阳生，岁回律转。今天是模拟测试，感觉有很多和分块有关的内容。我做的还是 div 2。

题解

下面是题解了。A，B，C，D 四道题，截止至癸卯年冬月廿五甲子月己巳日亥时，已经补完前三道题，D 已经理解了。补充，D 已经改完了。

A. 高尔夫

就是有个排成一排的坑，打杆球，然后最开始坑都是空的。每次选一个坑往左或往右打球，球会落在第一个空坑里，如果选择位置是空就会掉到选择位置的坑里。要求球不能打出场外。求方案数。这道题我用多项式生成函数搞了半天，没搞出通项，然后最后本来想打一个 70 分的暴力的，结果忘记应该用 EGF 所以爆零了。不得不说这个题真的不愿意给样例啊。

答案很简单，就一个式子。。可以证明。添加一个坑，围成一个环，答案就是最后一个坑里没球的方案数。由于是均匀的，所以没球的概率可知，答案就是这个。

B. 网络单纯形

不要被名字吓到了。其实。

形式化题意

给定一个个点，条边的连通无向图，边有边权。每个点有颜色，颜色标号为。

有次修改操作，每次修改一个点的颜色。你需要在每次修改后计算所有连接不同颜色点的边中边权的最小值。保证在每次修改后，图中至少存在两种颜色。

图可能有重边。

首先发现一定是最小生成树上的边。然后就有各种方法了。首先是一种我在考场上胡出来的方法。就是每个点维护一个儿子的颜色线段树，叶子用 multiset。

当然赛后发现一种很好的方法。kruskal 重构树。当一个点子树内颜色不同时答案一定大于等于这条边的值。而最小的边一定满足左右子树都同色。发现 dfs 序有两个叶子是相邻的，所以维护所有相邻的不同颜色的叶子的 lca 的权值就行。

很妙啊，用到了好多性质。比如一个连通块里有多个颜色一定是那个啥然后子树边长相邻叶子等等。很妙。都不用写线段树，还不用根号分治。

C. 原神账号

有个数字排成序列，第个数字为。有次询问，每次询问给定 个区间，你需要求出这些区间的并内不同的数字个数，强制在线。

请注意，本题的空间限制为 8MB。

。

考场上想到用 bitset + st 表，但不会优化了。正解是这样的，分块，假设分为块，每次询问中间的整块就用 st 表询问，剩下的散的暴力。由于同阶，就都看成。这样复杂度是。后面两个是询问的复杂度。空间复杂度是。经过计算可以开到将近 100。其实开到就行了，也就是最多分为 64 块就行。分块 + bitset 的题目，好爱。

D. 肖芬途

这不小粉兔吗？

给定一棵个点的有根树（节点标号为），以号点为根。其中号点的点权为。

假设号点的父节点为（方便起见认为），对于任意整数，满足。

有次询问，第次询问给出一个区间，求：

其中表示和的最近公共祖先。

本题强制在线。

。

这道题容易发现性质，可以发现点的顺序相当于是一层一层来的，就是 bfs 序。因此找到满足的最大，相当于按顺序找到下一层最后一个没有在这一层后几个点子树里的点。

然后范围内的点就构成了以为根的联通子树。然后就可以分块。暴力的话就是每加入一个点更新前面所有祖先的子树权值和平方。然后答案就相当于上面第二个区间里的区间求和。那么分块，每一个分块就是记录选择前缀点的时候点的子树点权前缀和，这里要卡一下空间。然后后缀多余的就暴力加进去。怎么算呢，就算的祖先，判断根是哪个，然后更改就行。要注意这里求祖先要使用长链剖分求，不然复杂度退化成，可能过不了。（如果你是卡常大师请无视我）。

生成函数

今天晚上 dzy 继续讲生成函数。哈哈，想起今天第一题用生成函数乱搞没有搞出来。

今天讲到了置换计数。

置换计数

一个置换是由若干轮换组成的集合。感觉很斯特林啊。

k 轮换的个数有个，对应 EGF 为。

所有轮换的 EGF 为

所有置换的 EGF 为

背包计数

有种物品，体积为的物品有种，每种物品无限/1个。

有种物品，第种体积为，有个。

求选取体积为的方案数。

n 个点树的个数（儿子都没有顺序）

• 有标号无根树：利用 prufer 数列可知答案是。
• 有标号有根树：每个有标号无根树对应 n 棵有标号有根树，故答案为
• 无标号有根树：前两个是 EGF，这个就是 OGF。

• 无标号无根树。

1. 背包。
2. 求和、求导、分治。
3. 。

后记

好呀。明天就回家啦！回家！