Day -?
和尊贵的 luogu 管理以及 zhafde fans club 群友组队，原因是想起来去年七月命名的 Alchemy 队名似乎还没用上（当时是用来申请 ucup，只是懒惰的我一次也没有打）。
然后群里转发了一个个人赛的链接，说每个队要派一个去打，然后我就稀里糊涂地报了名。
Day 0
2024.5.25.
发现个人赛可以不报名。OK。
讨论了板子问题，最后由 zhafde 整出高达 31 页的板子整理。恐怖如斯。我提出建议，筛法可以不带。
上午翘开幕式，然后简单试机，并且膜拜 wzj33300。午饭在真功夫等了半天，然后睡觉。13:57 醒来，父母都以为 14:30 开个人赛，而我看着选手牌上的 14:00，一路狂奔。结果到了才发现，怎么真的延误成了 14:30……
个人赛题意简述
A：给一个序列，多次询问如果去除下标在 [li,ri] 的元素，剩下来的任选三个数组成三角形，最大的周长是多少。无解输出 -1。n≤5×105，q≤106。
B：给一棵有根树。定义一个点集是好的，当且仅当其中任意两点的 LCA 为同一个点，且这个点在集合中。定义一个点集的集合是好的，当且仅当每个点集是好的，并且全部点在且恰好在一个点集中。忘了怎么算点集的集合的权值，反正要求全部好的点集集合的权值的加和或乘积。n≤200。
C：给一个正整数序列 a 表示 n 个人的初始分数。两个人打一场比赛的结果，是都加 1 分或者某一个人加 3 分。若每个人都打了 k 场比赛，求分数严格高于第一个人的分数的人数的最小值。2≤n≤105，1≤k≤10。
D：多次询问，构造方案，在 n×m 的棋盘上放 k 个马，使得它们两两不能攻击，规则用中国象棋的。t≤104，n,m≤103。
E：构造无限长的 01 字符串 S，Si 为 i 在二进制下 popcount 的奇偶性，i 从 0 开始。每次给一个含 0/1/? 的字符串，对每个前缀问每种给 ? 填 01 的方式中，前缀的在 S 中的子串个数的和。范围忘了，似乎是 105 级别。
F：简而言之是一道二合一，是入门题加背包和体积很大、价值比较小的多重背包。大到 1012。
G：有 n 块钱，要数有多少组正整数 (a,b,c)，满足 40a+39b+21c=n。n≤1016。
H：定义一个 n 个点的简单图是好的，当且仅当任意两点间的路径数目在 [k,k+1] 之间，给定 k，数好的图的个数。数据范围忘了。
历程
先看了会 A，没有秒。发了会呆，打算跟榜开题。然后开了 G，然后过了。
然后想明白了 A，有对数长度的性质。简而言之，就是最大的三个数 a,b,c 不能满足，那么 2c≤a，依此类推，所以最多暴力试 logV 次。然后写了个主席树，两只 log，被卡了。
然后再跟榜，看 C，发现好像有点麻烦。然后口胡了这样一个办法：a≤a1 和 a>a1+3k 的直接无视，可以让它们都赢来让中间的部分输。然后二分中间的部分有几个可以不超过 a1+3k，其余的直接全赢即可，这部分全赢的就挑较大的那些。这个地方的判定感觉有点模糊，直接写：记录每个点还给输的总次数和给平局的总次数，一胜二负可换三次平局，不行就 break。然后就过了，没有卡我，估计是数据造水了，感觉不是很严谨。
然后发现 A 不需要主席树，直接维护前/后缀的前 37 大就可以了。这个时候开始了智熄操作：两发罚时没删调试语句，两发罚时罚 iostream。从结果上看，这个失误直接导致了我掉出前 20。
切完三道签到，已经过了 100 min，感觉有点久了。榜上有别人做的就是 D，然后就想到矩形和等腰直角三角形是满足条件的。更广泛一点，一个八边形，其中只有横边、纵边、45 度边的，都是可以的。然后就想能不能枚举四个角，时间太久，没想到优化。
看了眼其他题，B 似乎最优做法是 n4，目测不好写也比较久。E、H 不可做。F，已经把题意拆成上面所述的了，然后发现不会这种大体积背包，然后放弃。
结束前 6 min，突然觉得 D 可以只枚举左上和右下的三角形，然后就慌了，以为会了。
赛后
讲了讲 D 做法，突然发现假了，那还是活该。
手动滚榜，一万个名字被读错，分辨率有点低下。
广州市铁一中学初二学子战绩斐然！祈福英语实验小学荣获 rk6！长沙市雅礼中学包揽 rk1,2！而且双双切下 B 题！
以为有讲题。
回来看题解，发现 B 正解就是 O(n4)，而 F 可以反转价值和体积，属于是智熄了一下。
没事，不过是热身。
Day 1
2024.5.26.
到处都是小情侣和女装大佬。
题意简述
A：给一些线段，数有多少个田字格，大概这样，不记得了。
B：给若干个字符串，求两两 LCPS 的长度总和，LCPS(A,B) 为最长的 s，满足 s 为 A 后缀、也为 B 前缀。∑∣S∣≤3×106。
C：忘了，因为我没做，但好像很简单。
D：超长题面，懒得读。
E：对 n 个点的竞赛图，有任选 m 个点，必有一个点指向其他所有点、必有一个点被其他所有点指向。求点的出度集合的最小大小。n,m 比较大，多测。
F：给一个无向图，找到一对 (u,v) 和 ⌈n−1m⌉ 个 u→v 的边不交的路径。n,m≤3×105。
G：10 次询问，每次给定 [l,r]，求 maxl≤x<y≤rgcd(x,y)。1≤l<r≤1012。
H：有 m 个盒子，n 个球。每个盒子有容量。编号为 i 的球操作时会从序列 ai 中找到最先的没满的盒子，然后投进去，如果没有就不投进去。给这些球排序，让它们依次操作，使得投进盒子的球数最大。输出最大球数及一种方案。t≤500，n≤500，m≤500，∑nm≤2.5×105。
I：有长为 n 的正整数序列 a，和 m 个限制，形如 axi≥ayi+azi，求最小的 ∑a，满足 ∑a≤109，无解输出 -1。忘了范围了。
J：考虑编号为 2∼n 的无向图，u,v 有边当且仅当 u∣v∨v∣u。求所有联通点对的编号乘积之和。n≤1011。
令人无语的赛程
有意思的是，被堵门一段时间才进场，没有人检查身份证，而且发现电脑仍未重置。
先跟会榜。突然发现智障地卡了 G 题，卡了一卡，感觉没很水的做法，还是写整除分块。反正过了 G、I、C，其中 heaksicn 在 I 题贡献了 2 发罚时，zhafde 通过了 C。
猜 J，heaksicn 提出是一大坨联通图再加比较大的一些质数的样子，觉得非常有道理。然后发现要求质数前缀和和质数平方前缀和。尝试场推 min_25 筛，式子推对了，时间全假了。加了记忆化，还是跑不动。一点不会实现，开摆。
队友写 E，暴力写挂，我实在急了，我说你要不猜吧，然后发现他猜的贼有道理，就是首项和末项猜一下，然后中间是一大串 n，然后公差为 2 下降。然后就 TLE 了，原来是 iostream 导致的。过了。至此，heaksicn 贡献了 4 发罚时，可见其贡献之大。
会了 B，知道是 AC 自动机，每个点直接 fail 子树 sum 乘上 trie 子树 sum，然后可能还要容斥。然后突然又不会了，想不清楚怎么计算“longest”。吃了点东西，又会了，发现可以让每一个都有贡献，算最长 border 就行。然后过了。这个东西呢，是两片面包夹着紫薯、蛋、番茄、鸡肉、生菜的矩形三明治，感觉味道很奇怪。
然后队友继续 H，这可是他们最喜欢的费用流。我猜 F，猜不到一点，只往找 dfs 树（后来看看这一部分本来应该对对脑电波的）、找点双、以及最大化最小割想，显然越想越偏。
还剩一个小时，一个 H 调不出来，急了。然后把输出排列的部分写拓扑排序（这玩意能写 40 min 有点绷不住），然后就 TLE 了，最后认为是费用流导致的。
什么？你问 A 和 D？加训 ds 的 zhafde 早就看了，并且表示不可做，从最终的榜上看，的确没人做。
虽然上了金线，也高于校另一队两名，但还是感觉遗憾。seanlsy 场推 min_25 筛，除了膜拜还有什么！广东实验中学初二如此强悍，还能说什么！
结局
打星没有任何 award。和同校的吃了个 KFC，然后跑路。
正如 zhafde fans club 群友所说，但凡带一个 min_25 板子（我愚笨的脑子还是实在想不起那个优秀的实现方法和时间的证明），但凡他把 F 题想到树的灵感拿出来讨论一下（其实好像也讨论不到那么妙的做法，虽然我隐约对过脑电波），（H 实在不知道咋回事，有人 zkw 费用流可过，让我们队很懵），其实很多缺憾都弥补了。
经验问题。实力问题。
然后在 Q 群和知乎吃瓜。
附件
贴一下个人赛的题解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
| ### A 水仙三角形
先考虑$O(n)$是可以回答每个询问的：枚举最大的木棒，那么剩下两个木棒的长度之和就需要最大，那么必然是小于当前长度的最小的两个。
因此对有序的数组，只需要检验相邻的三个即可。
考虑最大值如果不用，那么第二大和第三大的和小于等于它，那么第三大必然不超过最大值的一半
依次类推，如果第三大也不能是答案，那么第五大必然不超过第三大的一半
依次类推，经过$2logV$次之后，数值就会到达1，因此如果有解，最大值必然在前$40$大的值中。
维护前缀和后缀的前$40$大值，使用插入排序。
对于每个询问，把断开出的前缀和后缀合并成一个有序数组，求解，这里使用归并排序。
### B 分割树
一个点集 $V'$ 是好的，当且仅当其包含一个节点与它的某些儿子节点子树中的至多一个节点。也就是说，对于 $V'$ 中的点建立虚树，一定是一个菊花，且是根向下有若干条边。
一个点集的集合的权值是从其每个点集中选出一个位置，乘积之和。
考虑 $dp_{i,j,k}$ 表示 $i$ 子树内，有 $j+k$ 个剩余的不在某个点集的节点，其中 $j$ 个给乘积的贡献为 $1$，$k$ 个为 $a_x$ 的所有情况下，目前权值的和。
考虑转移，有以下两种情况：
\* 目前点 $i$ 是某个子集的“根”节点；
\* 目前点 $i$ 是某个子集的“叶子”节点。
对于第一种情况，设辅助数组 $f_{j,k,0/1}$，最后一维的含义是该子集是否钦定一个点给乘积的贡献为 $a_x$。有以下转移：
\* $f_{j_1,k_1,0}\times dp_{v,j_2,k_2}\to f'_{j_1+j_2,k_1+k_2,0}$；
\* $f_{j_1,k_1,1}\times dp_{v,j_2,k_2}\to f'_{j_1+j_2,k_1+k_2,1}$；
\* $f_{j_1,k_1,0}\times dp_{v,j_2,k_2}\to f'_{j_1+j_2-1,k_1+k_2,0}$；
\* $f_{j_1,k_1,1}\times dp_{v,j_2,k_2}\to f'_{j_1+j_2-1,k_1+k_2,1}$；
\* $f_{j_1,k_1,0}\times dp_{v,j_2,k_2}\to f'_{j_1+j_2,k_1+k_2-1,1}$。
最后 $f_{j,k,1}\to dp_{i,j,k}$。
对于第二种情况，设辅助数组 $g_{j,k}$。有以下转移：
\* $g_{j_1,k_1}\times dp_{v,j_2,k_2}\to g'_{j_1+j_2,k_1+k_2}$。
最后有：
\* $g_{j,k}\to dp_{i,j+1,k}$；
\* $g_{j,k}\times a_i\to dp_{i,j,k+1}$。
根据树上依赖背包的分析，总复杂度为 $O(n^4)$。
### C 乐乐买书
构造通解$z=2*k,x=77*k-38*n,y=39*n-79*k$,算出$k$的范围，为解的数量。
### D 马
考虑想几种构造方法然后拼起来。
不妨设 $n\ge m$。首先，对于 $k\le (n-2)m$ 的情况，我们可以先放一个满的矩形然后空两行再放一个前缀。然后由于现在无法处理的 $k$ 接近 $nm$，我们考虑从填满的棋盘里去掉一些点。这件事有多种实现方法，比如去除三个角上的等腰直角三角形（任意正整数均可以被不超过三个三角形数的和表示，而且这里三角形的边长由于是 $\sqrt{m}$ 量级因此在 $n,m$ 较大时不会重叠，$n,m$ 较小时此方法也能得出合法方案），或者去除连续的三条斜线再删掉角上的 $0\sim 2$ 个点等。
总之这个题应该有多种构造方法，如果你的方法比较烂可能有一些边界情况。
### E 字符串
记 $P_0$ 为题中给出的 $P$ 字符串，$P_1$ 为 $P_0$ 取反的结果。
记 $S_{l\sim r}$ 在 $l\le r$ 时表示 $S_lS_{l+1}\dots S_{r}$，在 $l>r$ 时，表示 $S_lS_{l-1}\dots S_{r}$。
首先可以发现 $P_{0,i}=\operatorname{popcount(i)}\mod 2$。
其次考虑找到 $P_0$ 子串的性质。
> Lemma.1：若 $S$ 为 $P_0$ 的子串且 $|S|>1$，则存在拆分点 $i\in [1,|S|)$，使得 $T_{i-1\sim 0}=P_{0/1,0\sim i-1} \land T_{i\sim |S|-1}=P_{0/1,0\sim |S|-i-1}$。
>
> 简单地说，就是可以把 $S$ 拆分成两个串 $T_1,T_2$，使得 $T_2$ 是 $P_{0/1}$ 的前缀，$\operatorname{rev}(T_1)$ 是 $P_{0/1}$ 的前缀（$\operatorname{rev}$ 是字符串翻转）。
>
> 证明的话，设 $S$ 为 $P_{0,l\sim r}$，那么找到 $(l,r]$ 中 $\operatorname{ctz}$ 最大的 $i$，那么 $i-1$ 就是一个合法的拆分点。简单地说，就是找到进位最大的一次，后面的是 $P_{P_{0,i}}$ 的前缀，前面的翻转是 $P_{P_{0,i-1}}$ 的前缀。
然后同时可以发现，Lemma.1 的逆命题也是真命题，即存在拆分点的串一定是 $P_0$ 的子串，证明考虑构造即可。
> Lemma.2：若 $S$ 是 $P_0$ 的子串且 $|S|>1$，同时取出 $S$ 的两个拆分点 $i,j$，那么 $|i-j|=2^k(k\ge 0)$。
>
> 这个很好理解，$i,j$ 中间这一段正反都要是 $P_{0/1}$ 的前缀，长度只能是 $2^k$。
注意到 Lemma.2 同时也说明了一个串的拆分点个数 $\le 3$，当个数 $>3$ 的时候必然会有一对点不满足距离是 $2^k$ 的限制。
但是其实拆分点个数有更加紧的上界 $2$，如下：
> Lemma.3：若 $S$ 是 $P_0$ 的子串且 $|S|>1$，那么 $S$ 的拆分点至多只有两个。
>
> 证明并不难，考虑反证法：若有三个拆分点 $a,b,c(b-a=c-b=2^k)$，那么 $S_{b\sim c-1}$ 和 $S_{a\sim b-1}$ 正好互补，同时要求了 $S_{c}=1-S_{b}=1-S_{a}$，推出矛盾。
>
> 当然，你也可以尝试把长度 $\le n$ 的串都找一遍拆分点并输出，发现这个性质。
到这里，我们先考虑如何计算 $g(S)$，发现只需要计算所有串拆分点的个数减去拆分点有 $2$ 个的串的个数。
计算有拆分点的串个数：枚举拆分点位置，计算左右最多能匹配 $P_{0/1}$ 多远，乘起来贡献到答案。
计算拆分点有 $2$ 个的串的个数：枚举拆分点距离 $2^k$，枚举两个拆分点 $i,j$，向左向右匹配至多 $2^k$，相乘贡献到答案。
至于区间匹配 $P_{0/1}$ 的问题，可以使用倍增轻松解决。
接下来，考虑计算 $k=|S|$ 时的答案。
发现当拆分点在 $i$ 处时，向左匹配到 $j$，则贡献就是：
$$
(i-j)\times 2^{pre_j}+\sum_{x=j+1}^{i}[S_x = \texttt{?}](i-x)\times 2^{pre_{x-1}}
$$
其中，$pre_x=\sum\limits_{i\le x}[S_i=\texttt{?}]$。
预处理一下 $\sum\limits_{x\le i}[S_x=\texttt{?}]\times 2^{pre_{x-1}}$ 和 $\sum\limits_{x\le i}[S_x=\texttt{?}]\times x\times 2^{pre_{x-1}}$ 即可。
向右匹配同理，计算完两边答案乘起来就行。
拆分点个数为 $2$ 的同理计算，这里不赘述。
一些小细节：
- 多测注意清空；
- 子串长度为 $1$ 的情况特殊处理；
最后，对于 $k<|S|$ 的答案，发现每一次贡献答案时对于 $k$ 都是一段区间加，所以差分一下即可，具体细节参见代码。
时间复杂度：$\mathcal{O}(n\log n)$，空间复杂度：$\mathcal{O}(n+\frac{n\log n}{\omega})$。
题外话：本来是想出成区间询问的，奈何写出来的程序效率极差，常数非常大，所以降低了难度，出成前缀询问的。
### F 出题
首先考虑第一个部分的性质。我们分两部分分析区间的个数：
- 一端点是原区间端点的：这样的区间个数每个加入的区间至多会产生 $2q$ 个。
- 两端点都是被截断出来的：可以证明，这样的区间个数至多为 $2q$ 个。
我们只需要证明这样的区间两两不交或包含即可。反证，假设两个区间相交，左边区间为 $[l_1,r_1]$，右边区间为 $[l_2,r_2]$，并且 $l_1<l_2<r_1<r_2$，则 $[l_1,r_1]$ 加入时间早于断点 $r_1$ 加入时间，并且晚于断点 $l_2$ 加入时间，$[l_2,r_2]$ 加入时间早于断点 $l_2$ 加入时间，晚于断点 $r_1$ 加入时间，矛盾。因此区间两两不交或包含，那么总区间个数只有二倍断点个数个。
因此原问题可以被转化成价值总和比较小的多重背包问题。考虑将物品二进制拆分。设 $f_{i,j}$ 表示处理完所有个数 $\geq 2^i$ 的物品，价值总和为 $j$ 的最小体积，转移只需要枚举每个个数为 $2^{i-1}$ 的物品然后转移即可。
但是这样时间复杂度爆炸，因为 $j$ 的范围并没有保证。考虑个数小于 $2^{i}$ 的物品的价值之和，显然不会超过 $2^{i+2}\sum q$，因此，我们只需要找到最大的 $j$ 满足 $f_{i,j}\leq T$，然后保留 $[j-2^{i+2}\sum q,j]$ 范围内的状态进行下一层 DP 即可，这样 DP 的复杂度是 $O(n\sum q\log T)$ 的。
前半部分直接暴力 $O(\sum q^2)$ 即可通过。$O(\sum q^2\log q)$ 可能会被卡常。
Bonus：DP 的复杂度实际上可以做到 $O(n\sum q\log (\max q\sum q))$。
### G 比赛
对于非平局的情况（首先局数一定$\ge2k$，因为一号选手肯定是赢$k$把），不难发现只要赢的局数大于等于输的局数就一定存在合法匹配。
对于非平局的情况，直接设到状态里面，具体的，设$f_{i,j}$表示前$i$个人，剩下$j$个平局待匹配。
显然$j\le k$，每次枚举匹配多少个平局，剩下的贪心分配。
把人按照分从小到大排序，显然舍弃的会是一个后缀，所以直接$dp$即可，时间复杂度$O(nk^3)$。
### H 橙汁计划
首先题意是将一个森林补全为树或者基环树的方案数。
考虑先求一下将所有连通块拼成一棵树的方案数，不难发现就是下面这个东西：
$$
n^{|S| - 2} \times \prod_{x \in S} siz_x
$$
这是因为考虑在长度为 $|S|-2$ 的 prufer 序列中填写 $1$ 到 $n$ 的项表示每条边被删除的时候连向的点，乘上每个连通块删除时最后连边的方案数。
现在考虑枚举连通块集合 $T$ 形成了一个环，那么对于 $|T| > 2$ 的情况，方案数应该是这么个东西：
$$
n^{|S| - 2} \times \prod_{x \in S} siz_x \times n^{1 - |T|} \times \prod_{x \in T} siz_x \times \sum_{x \in T} siz_x \times \frac{(|T| - 1)!}{2}
$$
大概意思就是把树的方案数中扣掉环的连通块，然后对环的每个连通块取两个点连到别的连通块。$(|T| - 1)!$ 算的是有向环的数量，因此要除以 $2$。
考虑对每个 $|T|$ 算出对应的系数。显然麻烦的部分只有 $\prod_{x \in T} siz_x \times \sum_{x \in T} siz_x$，等价于 $\prod_{x \in T} siz_x \times \sum_{x \in S} siz_x - \prod_{x \in T} siz_x \times \sum_{x \not\in T} siz_x$，显然后半部分的式子可以将求和拆开从而改写成 $\prod_{x \in T} siz_x$ 乘上一些容易计算的项的形式，所以我们的任务变为求多项式 $\sum_T x^{|T|}\prod_{y\in T}siz_y=\prod_{y\in S}(siz_yx+1)$。
这可以用分治 NTT 做到 $O(n\log^2 n)$。考虑如何优化。
注意到因为 $\sum siz_x=n$，所以我们可以将完全相同的项用二项式定理直接乘起来，然后按照 $siz_x$ 从大到小暴力 NTT 合并所有多项式，合并所有项的复杂度为 $\sum_{i=1}^n [c_i](c_i+\sum_{j>i} c_j)=O(\sum_i c_i\cdot i)=O(n)$，其中 $c_i=\sum_{x\in S}[siz_x=i]$。算上 NTT 的复杂度，总复杂度为 $O(n\log n)$。
|