者，山间之朝暮也；野芳发而幽香，佳木秀而繁阴，风霜高洁，水落而石出者，山间之四时也。朝而往暮而归，四时之景不同，而乐亦无穷也。
嗯就是看大家都写了做题记录我也不能闲着，所以搞个口胡题记录。
Week 的划分到周末/节假日结束，嗯对。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
WEEK 1（2026.3.31 - 2026.4.6）
P15654
link。
ABC452E
Difficulty：4.1 / Easy
题意解析：给定两个长度分别为 n,mn,mn,m 的数组 A,BA,BA,B，求 (∑i=1n∑j=1mAiBj(i mod j)) mod 998244353(\sum_{i=1}^n\sum_{j=1}^m A_iB_j(i\bmod j))\bmod 998244353(∑i=1n ∑j=1m Ai Bj (imodj))mod998244353。
枚举 iii 没啥前途，考虑枚举 jjj。
考虑设置阈值 lll，j≤lj\le lj≤l 直接 O(n)O(n)O(n) 暴力。现在考虑 j>lj\gt lj>l。
注意到第三个乘数一定是 1,2,3,4,...,j−1,0,1,2,3,...1,2,3,4,...,j-1,0,1,2,3,...1,2,3,4,...,j−1,0,1,2,3,... 循环，而且循环次数一定不超过 nj\frac{n}{j}jn 次。所以考虑前缀和处理 ∑Ai\sum A_i∑Ai 与 ∑Ai×i\sum A_i\times i∑Ai ×i，然后减一下就行了。
这样就是 O(nl+∑j=l+1mnj)O(nl+\sum_{j=l+1}^m \frac{n}{j})O(nl+∑j=l+1m jn ) 的，lll 取 000 时有 O(∑j=1mnj)=O(nlogm)O(\sum_{j=1}^m \frac{n}{j})=O(n\log m)O(∑j=1m jn )=O(nlogm)。
record
P6572
Difficulty：4.3 / Template
虚树板子题。
虚树板子题不讲如何建虚树等于废话。
如何建虚树？
首先把关键点按 dfn 排序。然后所有相邻两个的 LCA 一定是这棵虚树的关键点。而且用这些就能描述这一棵虚树了。
::::success[证明]
感性理解不难，说白了懒得证。
那这个和废话没啥区别了（逃
::::
然后再把这些点按 dfn 排序，将每个点与它和上个点的 LCA 相连，就是这一整棵虚树了。
::::info[证明]
上个我都没证，你还想让我证这个？
::::
好了，建完虚树就简单了，套个树上差分板子就行了。
O(nlogn+∑slogs)O(n\log n+\sum s\log s)O(nlogn+∑slogs)。
record
不行，写的题还是太多了，再这么搞下去我这个就是做题记录而不是口胡题记录了。
WEEK 2(4.7 / 4.13上午)
发烧了，写不了题了，那咋办。
没事应该可以加时一天。虽然也写不了什么题就是了。
P16256
场切，爽！
Difficulty: 4.0 / Easy+
考虑每一个 iii 的贡献。注意到这个贡献是独立的，不受前面（除 i−1i-1i−1）贡献情况的影响。因此可以单独计算。
定义 pre(Ai)\text{pre}(A_i)pre(Ai ) 为 maxj=1iAj\max_{j=1}^i A_jmaxj=1i Aj ，显然如果满足 pre(Bi−1)≤pre(Ai−1),pre(Bi)>pre(Ai)\text{pre}(B_{i-1})\le \text{pre}(A_{i-1}),\text{pre}(B_i)\gt \text{pre}(A_i)pre(Bi−1 )≤pre(Ai−1 ),pre(Bi )>pre(Ai ) 或 pre(Bi−1)>pre(Ai−1),pre(Bi)≤pre(Ai)\text{pre}(B_{i-1})\gt
\text{pre}(A_{i-1}),\text{pre}(B_i)\le \text{pre}(A_i)pre(Bi−1 )>pre(Ai−1 ),pre(Bi )≤pre(Ai )，则会产生 111 的贡献。把它们分别计作情况 1，情况 2。
情况 1
显然前 i−1i-1i−1 要在 [1,pre(Ai−1)][1,\text{pre}(A_{i-1})][1,pre(Ai−1 )] 之间选，iii 要在 (pre(Ai),n](\text{pre}(A_i),n](pre(Ai ),n] 之间选，剩下的随便选。总情况数为 (pre(Ai−1)i−1)(i−1)!(n−pre(Ai))(n−i)!{\text{pre}(A_{i-1})\choose i-1}(i-1)!(n-\text{pre}(A_i))(n-i)!(i−1pre(Ai−1 ) )(i−1)!(n−pre(Ai ))(n−i)!。
情况 2
前 i−1i-1i−1 都要在 [1,pre(Ai)][1,\text{pre}(A_i)][1,pre(Ai )] 选，但必须至少有一个要大于 pre(Ai−1)\text{pre}(A_{i-1})pre(Ai−1 )。这太难了。
考虑反向统计，总方案数为 (pre(Ai)i−1)(i−1)!{\text{pre}(A_i)\choose i-1}(i-1)!(i−1pre(Ai ) )(i−1)!，不合法的有 (pre(Ai−1)i−1)(i−1)!{\text{pre}(A_{i-1})\choose i-1}(i-1)!(i−1pre(Ai−1 ) )(i−1)!，所以合法的有 [(pre(Ai)i−1)−(pre(Ai−1)i−1)](i−1)!。
再用方案 1 同种方法考虑后面的，总贡献数为 [(pre(Ai)i−1)−(pre(Ai−1)i−1)](i−1)!(pre(Ai)−i+1)(n−i)!(\text{pre}(A_i)-i+1)(n-i)!(pre(Ai )−i+1)(n−i)!。
时间复杂度：O(n)O(n)O(n)。
record
WEEK 3(4.13下午 / 4.19)
P1084
恭喜口胡题又添一名大将！
Difficulty：4.7 / Easy
无脑考虑二分答案。
显然跳到儿子节点纯何意味，肯定要一直往根跳。
然后会发现这样还不够，因为可能有一些点可以跨过根去支援其它子树。
所以我们每个子树，如果全移到根已经可以守住就全移到根，否则留一个时间最少的，其它全移到根。
然后到根的所有节点剩余时间和到剩下子树的距离比较，看看能不能匹配。
O(nlognlogV)O(n\log n\log V)O(nlognlogV)，但 0 个人想写。
