[NOI 2026] 线段
简单题。
题目链接： [NOI 2026] 线段 。
题目描述：
给若干个区间，对于每一个 s=1,2,⋯ ,ks=1,2,\cdots,ks=1,2,⋯,k ，求大小恰好为 sss 的区间构成的子集的区间图联通无环的方案数。
n≤3000,m≤1000,k≤200n\le3000,m\le1000,k\le200n≤3000,m≤1000,k≤200 。
li,ri∈[1,m]l_i,r_i \in [1,m]li,ri∈[1,m] 。
定义 fi,j,kf_{i,j,k}fi,j,k 表示右端点为 iii ，次右为 jjj ，个数为 kkk 的方案数。
那么考虑选择的集合是否超出 iii ：
超出，此时有 fi,j,k→frp,i,k+1f_{i,j,k}\to f_{r_p,i,k+1}fi,j,k→frp,i,k+1 。
不超出，此时有 fi,j,k→fi,rp,k+1f_{i,j,k}\to f_{i,r_p,k+1}fi,j,k→fi,rp,k+1 。
对着转移就行，代码不放了。
PS: 直接转移是 O(nm2k)O( ...
Burnside 引理
强壮的 Burnside 引理，羸弱的 Polya 定理。
轨道—稳定子定理
给定群 GGG 对集合 XXX 的群作用。
定义群作用下 g∈Gg\in Gg∈G 的不动点集合为 Fix(g)={x∣gx=x}⊆XFix(g)=\{x|gx=x\}\subseteq XFix(g)={x∣gx=x}⊆X 。
定义群作用下 x∈Xx\in Xx∈X 的不动群元素集合为 Stab(x)={g∣gx=x}⊆GStab(x)=\{g|gx=x\}\subseteq GStab(x)={g∣gx=x}⊆G 。
易得 Stab(x)Stab(x)Stab(x) 是封闭的，也就是说， Stab(x)Stab(x)Stab(x) 为 GGG 的一个子群。因此 Stab(x)Stab(x)Stab(x) 也被称为稳定子群。
定义元素 x∈Xx\in Xx∈X 的轨道为 Orb(x)={gx∣g∈G}Orb(x)=\{gx|g\in G\}Orb(x)={gx∣g∈G} 。
那么就有轨道—稳定子定理：
∣G∣=∣Stab(x)∣×∣Orb(x)∣|G|=|Stab(x)|\tim ...
CF850F Rainbow Balls
用期望势能函数做了一下，发现很简单。
题目链接： CF850F Rainbow Balls 。
题目描述：
有 nnn 种颜色，每种颜色有 aia_iai 个球。
每秒随机两个球 iii 和 jjj ，将 jjj 的颜色变成 iii 的。
当所有球颜色一样时，游戏结束。
求游戏期望秒数。
经典套路。
令 m=∑aim=\sum a_im=∑ai ， kkk 为当前剩余颜色个数， ϕ(a1,a2,⋯ ,ak)\phi(a_1,a_2,\cdots,a_k)ϕ(a1,a2,⋯,ak) 表示局面为 (a1,a2,⋯ ,ak)(a_1,a_2,\cdots,a_k)(a1,a2,⋯,ak) 时的势能函数。
设 ϕ(a1,a2,⋯ ,ak)=∑g(ai)\phi(a_1,a_2,\cdots,a_k)=\sum g(a_i)ϕ(a1,a2,⋯,ak)=∑g(ai)
那么为了满足条件，有 ∑E[Δg(ai)]=−1\sum E[\Delta g(a_i)]=-1∑E[Δg(ai)]=−1
然后，对于 iii ，有：
E[Δg ...
[JOISC 2017] 自然公园 / Natural Park
NOIPlus 模拟赛 T4 放这个……
题目链接： [JOISC 2017] 自然公园 / Natural Park 。
题目描述：
有一个未知的 nnn 个点 mmm 个边的无向连通图，点编号 000 到 n−1n-1n−1 。
每次你可以调用 Ask(A,B,Place[]) 来询问只经过 Place[]Place[]Place[] 中的点时是否能从 AAA 到 BBB 。需满足 AAA 和 BBB 在点集中且 A<BA<BA<B 。 Place[]Place[]Place[] 是一个数组， Place[i]=1Place[i]=1Place[i]=1 表示可以经过 iii ， Place[i]=0Place[i]=0Place[i]=0 表示不可以经过 iii 。
Ask 操作调用次数不能超过 450004500045000 次。
你需要还原出这个无向连通图的每一个边，你可以调用 Answer(A,B) 来报告一条边，需满足 A<BA<BA<B 。
你需要实现函数 Dete ...
HDU20260723F 合成大 HDU
waw ，这是被出题人认为最难的一档题，我们居然做出来了。
题目描述：
构造仅包含 h ， d 和 u 的字符串 SSS ，满足 ∣S∣≤3001|S|\le3001∣S∣≤3001 且 SSS 里恰包含 nnn 个 hdu 子序列。
n≤109n\le10^9n≤109
神奇的写题历程。
这题是我和 WaterM 一起解决的。
一下是无聊的对话（回忆的，不保证百分百一样）：
……
WaterM ：你们对 F 有什么想法？
wzh ：根据 n 大小分类讨论。
WaterM ：详细点？
wzh ：大概就是如果 n<1e6n<1e6n<1e6 时固定一个右边的 u ，剩下全用 hd ，变为 hd 子序列计数。 nnn 大的时候就多搞点 uuu ，然后再调整。
WaterM ：想想……
wzh ：大概就把 nnn 按照 1,3,6⋯1,3,6\cdots1,3,6⋯ 拆分。
WaterM ：不对，达不到 1e9 。
wzh ：那就在末尾补一些 hhh...ddd...uuu... 。
WaterM ：想想……
WaterM ...
期望势能函数及其应用
定义
对于样本 X∈ΩX\in \OmegaX∈Ω ，定义其势能函数为 ϕ(X)\phi(X)ϕ(X) 。
若势能函数 ϕ\phiϕ 满足对于任意样本 Xt∈ΩX_t\in\OmegaXt∈Ω ，有：
E[ϕ(Xt+1)∣Xt]=ϕ(Xt)−1E[\phi(X_{t+1})|X_t]=\phi(X_t)-1
E[ϕ(Xt+1)∣Xt]=ϕ(Xt)−1
则从样本 sss 到样本 ttt 的期望操作次数为 ϕ(s)−ϕ(t)\phi(s)-\phi(t)ϕ(s)−ϕ(t) 。
证明好像要用到一个叫做 鞅的时停定理 的东西，很复杂，不过这里给一个不那么完善的简单证明。
特别的，这个势能函数往往需要根据题目猜测。
证明
让我们看看势能函数的条件到底是什么。
E[ϕ(Xt+1)∣Xt]=∑XPr[Xt+1=X∣Xt]ϕ(X)ϕ(Xt)=1+E[ϕ(Xt+1)∣Xt]=1+∑XPr[Xt+1=X∣Xt]ϕ(X)\begin{aligned}
E[\phi(X_{t+1})|X_t] &=\sum_{X}Pr[X_{t+1}=X|X_t]\phi(X)\\ ...
CF1019E Raining season
一辈子也不写闵可夫斯基和了。
题目链接： CF1019E Raining season 。
题目描述：
给一棵树，边权是一次函数 aix+bia_ix+b_iaix+bi 的形式。求当 x=0,1,⋯ ,m−1x=0,1,\cdots,m-1x=0,1,⋯,m−1 时的树的直径。
n≤105,m≤106n\le10^5,m\le10^6n≤105,m≤106 。
首先对于某一个路径的一次函数 kx+bkx+bkx+b ，为了求在 x=0,1,⋯ ,m−1x=0,1,\cdots,m-1x=0,1,⋯,m−1 时的最值，我们应该把他表示为平面直角坐标系的 (k,b)(k,b)(k,b) ，那么最后的答案就是所有路径的点对的凸包。
然后对于路径，我们应该点分治。那么对于一次的分治中心 xxx ，我们应该求出他的分治子树的所有点到 xxx 的路径的点对所形成的凸包。最后在把每个分治中心得到的凸包暴力合并就行了。问题在于如何合并两条从 xxx 出发路径。容易发现原来的 (k1,b1)(k_1,b_1)(k1,b1) 和 (k2,b2) ...
[WC2018] 通道
genlib 真是太好用了。
题目链接： [WC2018] 通道 。
题目描述：
给你三棵树 T1,T2,T3T_1,T_2,T_3T1,T2,T3 。
求 maxa,b{dist1(a,b)+dist2(a,b)+dist3(a,b)}\max\limits_{a,b}\{dist_1(a,b)+dist_2(a,b)+dist_3(a,b)\}a,bmax{dist1(a,b)+dist2(a,b)+dist3(a,b)} 。
n≤105n\le 10^5n≤105 。
这一看就是一个类似树的直径的东西。于是考虑边分治。在 T1T_1T1 上边分治后会得到左右两个点集，不妨记为 A,BA,BA,B 。设这些点到其中一个中心边的端点的距离为 valaval_avala ，那么就有 dist1(a,b)=vala+valbdist_1(a,b)=val_a+val_bdist1(a,b)=vala+valb ，其中 a∈A,b∈Ba\in A,b\in Ba∈A,b∈B 。
此时式子变为最大化 vala+valb+dist2(a, ...
「Daily OI Round 1」Memory
考试考三道题目都是线段树题目，写爽了。
考完试发现是自己场切两个紫题\textcolor{purple}{紫题}紫题 ，写一篇题解纪念。
题目链接： 「Daily OI Round 1」Memory 。
题目内容：
有 nnn 条线段 [li,ri][l_i,r_i][li,ri] ，每条线段有颜色 cic_ici 和权值 wiw_iwi 。
一个由线段构成的集合 MMM 合法当且仅当对于任意两条不同的线段 i,j∈Mi,j \in Mi,j∈M ，有 ci=cjc_i=c_jci=cj 或 [li,ri]∩[lj,rj]=∅[l_i,r_i]\cap [l_j,r_j]=\varnothing[li,ri]∩[lj,rj]=∅ 。这个集合的权值为 ∑i∈Mwi\sum\limits_{i\in M}w_ii∈M∑wi 。
求权值最大的集合的权值。
n≤105n\le 10^5n≤105 。
显然 DP 题目。
为了处理交集为空的限制，先按右端点排序，然后定义 fi,jf_{i,j}fi,j 为前 iii ...
[ICPC 2023 Jinan R] 向未来说你好
对你说再见。
题目链接： [ICPC 2023 Jinan R] 向未来说你好 。
题目内容：
给定长度为 nnn 的序列 aaa 的一个合法的子段划分为：设第 iii 个子段左右端点为 li,ril_i,r_ili,ri ，则需满足：
∀i, ∀j∈[li,ri], ,aj≤ri−li+1\forall i,\ \forall j\in [l_i,r_i],\ ,a_j\le r_i-l_i+1
∀i, ∀j∈[li,ri], ,aj≤ri−li+1
对于任意一个 iii ，求当 aia_iai 变为 111 ，合法子段划分数。
先考虑不带修改的情况。
设 fif_ifi 为以 iii 为结尾的合法字段划分总数，初始 f0=1f_0=1f0=1 ，则有：
fi=∑{fj ∣ ∀k∈[j+1,i], ak≤i−j}f_i=\sum\{f_j\ |\ \forall k\in[j+1,i],\ a_k\le i-j\}
fi=∑{fj& ...
