FUN WORLD

Day 1, T1. 卡牌游戏 题意：有 nnn 张牌，第 iii 张牌正面写着数字 aia_iai​，背面写着数字 bib_ibi​，初始时正面向上。请你选择 mmm 张牌翻面，使翻面后所有朝上的数字极差（最大值减最小值）最小。 m<n≤106m<n\le10^6m<n≤106，1≤ai,bi≤1091\le a_i,b_i\le10^91≤ai​,bi​≤109，保证所有 ai,bia_i,b_iai​,bi​ 互不相同，ai<ai+1a_i<a_{i+1}ai​<ai+1​。 答案一定是翻牌的一个前缀和一个后缀，即牌 1∼l1\sim l1∼l 为背面，l+1∼r−1l+1\sim r-1l+1∼r−1 为正面，r∼nr\sim nr∼n 为背面。 而且，最优解时一定不会出现 i∈[1,l],ai>bii\in[1,l],a_i>b_ii∈[1,l],ai​>bi​。同理也不会有 i∈[r,n],ai<bii\in[r,n],a_i<b_ii∈[r,n],ai​<bi​。这是因为翻前缀是要使最小值增大， ...

置换群 一个群，满足： 封：封闭性 结：结合律 幺：幺元（单位元） 逆：逆元 交：交换律 Burnside 引理 ∣S/T∣=1∣T∣∑P∈T∑a∈S[P∘a=a]|S/T|=\frac1{|T|}\sum_{P\in T}\sum_{a\in S}[P\circ a=a] ∣S/T∣=∣T∣1​P∈T∑​a∈S∑​[P∘a=a] 其中 ∣S/T∣|S/T|∣S/T∣ 表示 SSS 对 TTT 的商群，即同构的重复元素只算一次。 Polya 引理（Pólya） 针对 SSS 集合为一类固定格子个数 nnn、固定颜色个数 mmm、每个格子独立选择一种颜色填上的问题（TTT 为任意置换群）。有： ∣S/T∣=1∣T∣∑P∈Tmc(P)|S/T|=\frac1{|T|}\sum_{P\in T}m^{c(P)} ∣S/T∣=∣T∣1​P∈T∑​mc(P) 其中 c(P)c(P)c(P) 表示 PPP 的环个数。 应用：大多数时候会按 c(P)c(P)c(P) 分类。 容斥算 Burnside 下面 ans(x)\text{ans}(x)ans(x) 表示 ...

Statement 给你一棵 nnn 个点的森林，点有黑白两种颜色，初始时全为白色，边带权。初始时森林有 mmm 条边。请你支持 qqq 次操作：加边；删边；翻转 uuu 的颜色；询问 uuu 所在的树中所有黑点到它的距离之和。 数据范围：m<n≤105m<n\le10^5m<n≤105，k≤3×105k\le3\times10^5k≤3×105，∣w∣≤107|w|\le10^7∣w∣≤107。 Solution 边权肯定要拆成点权。难点主要是 LCT 的 MakeRoot 中，翻转根节点时不能维护好答案。所以对于每个 xxx，要维护到所在 Splay 深度最浅的点的距离和，以及到所在 Splay 深度最深的点的距离和。 具体而言，对于每个 xxx，都需要维护： 颜色（111 为黑，虚拟节点全为白）：col\text{col}col 虚子树内黑点个数：vcnt\text{vcnt}vcnt 虚子树和 Splay 子树内黑点个数：cnt\text{cnt}cnt 虚子树内黑点到 xxx 的距离和：vans\text{vans}vans 虚子树和 Splay 子 ...

Statement 给你 nnn 个点的空白图（即初始时没有边）。请你支持：加边；求 xxx 所在连通块重心；求所有连通块重心的异或和。保证任何时刻图是森林。 数据范围：n≤105n\le10^5n≤105，m≤2×105m\le2\times10^5m≤2×105。 Solution 树的重心的性质可以看 这里。 Algorithm 1 这个做法需要用到的树的重心的性质： 一棵树添加一个点，重心最多移动一条边。 删掉重心后，最大连通块大小小于等于总结点个数的一半。 根据性质 1，合并两棵树时我们启发式合并，暴力地将较小的那棵树中的点一个一个地插入较大的那棵树。 用 LCT 维护子树大小，对每个点维护两个值：所有虚儿子子树大小之和 vir\text{vir}vir，Splay 上子树内所有点的虚儿子子树大小之和 sum\text{sum}sum。查询点 xxx 的子树大小，可以将它旋转成所在 Splay 的根，然后求 sum(x)+vir(rson(x))+1\text{sum}(x)+\text{vir}(\text{rson}(x))+1sum(x)+vir(rson( ...

组合数 二项式定理：(a+b)n=∑r=0n(nr)an−rbr(a+b)^n=\sum_{r=0}^n\binom nra^{n-r}b^r(a+b)n=∑r=0n​(rn​)an−rbr 范德蒙恒等式：(n+mk)=∑i=0k(ni)(mk−i)\binom{n+m}k=\sum_{i=0}^k\binom ni\binom m{k-i}(kn+m​)=∑i=0k​(in​)(k−im​) 推论：mn(nm)=(n−1m−1)\frac mn\binom nm=\binom{n-1}{m-1}nm​(mn​)=(m−1n−1​) 或 (nm)m=(n−1m−1)n\binom nmm=\binom{n-1}{m-1}n(mn​)m=(m−1n−1​)n 错排列 前 777 项： D0D_0D0​ D1D_1D1​ D2D_2D2​ D3D_3D3​ D4D_4D4​ D5D_5D5​ D6D_6D6​ D7D_7D7​ 000 000 111 222 999 444444 265265265 185418541854 ⋯\cdots⋯ 公 ...

拉格朗日插值 给出 nnn 个点 (xi,yi)(x_i,y_i)(xi​,yi​)，求出过这 nnn 个点的 n−1n-1n−1 次多项式 L(x)L(x)L(x)。 拉格朗日插值多项式： L(x)=∑i=0n∏j≠i(x−xj)∏j≠i(xi−xj)⋅yiL(x)=\sum_{i=0}^n\frac{\prod_{j\ne i}(x-x_j)}{\prod_{j\ne i}(x_i-x_j)}\cdot y_i L(x)=i=0∑n​∏j=i​(xi​−xj​)∏j=i​(x−xj​)​⋅yi​ 时间复杂度 O(n2)O(n^2)O(n2)。 快速傅里叶变换 FFT 单位根 定义：ωn=e2πin=cos⁡(2πn)+i⋅sin⁡(2πn)\omega_n=e^{\frac{2\pi i}n}=\cos(\frac{2\pi}n)+i\cdot\sin(\frac{2\pi}n)ωn​=en2πi​=cos(n2π​)+i⋅sin(n2π​)。 两个复数相乘，模长相乘，幅角相加。 性质： ω2nn+k=−ω2nk\omega_{2n}^{n+k}=-\omeg ...

Statement 给出 nnn 个模板串 SiS_iSi​，求合法字符串个数，满足：可以被划分成非空的两段，使得其中每一段都是一个模板串的前缀。 数据范围：n≤104n\le10^4n≤104，∣Si∣≤30|S_i|\le30∣Si​∣≤30，∣Σ∣≤26|\Sigma|\le26∣Σ∣≤26。 Solution 如果看过网上的一些题解觉得没懂，那么你可以考虑看看这篇题解。 考虑用字符串总数减去重复字符串个数。对模板串建立 Trie，全集为 Trie 树节点数（不含根节点）的平方。 重复字符串形如：1 2 3∣41 2∣3 41∣2 3 4\begin{aligned}1~2~3|4\\1~2|3~4\\1|2~3~4\end{aligned}1 2 3∣41 2∣3 41∣2 3 4​，其中每个数字表示一段字符串。这个字符串在枚举 444、3 43~43 4 和 2 3 42~3~42 3 4 时都会被枚举到。 可以发现 AC 自动机上 3 43~43 4 的 fail 正好指向 444，2 3 42~3~42 3 4 的 fail 正好指向 3 43~43 4；所以考虑在 ...

Statement 给定字符串 sss，定义前缀 iii 表示 s[1:i]s[1:i]s[1:i]。mmm 次询问，每次询问给出两个数 l,rl,rl,r，求从前缀 l∼rl\sim rl∼r 中选出两个前缀的所有方案中，这两个前缀的最长公共后缀长度的最大值。 数据范围：∣s∣≤105|s|\le10^5∣s∣≤105，∣Σ∣≤2|\Sigma|\le2∣Σ∣≤2。 Solution 题目可以转化为后缀树上点集 SSS 中选两个点的 LCA 的 maxlen\text{maxlen}maxlen 最大值，即 max⁡i∈S,j∈S,i≠j{maxlen(LCA(i,j))}\max\limits_{i\in S,j\in S,i\ne j}\{\text{maxlen}(\text{LCA}(i,j))\}i∈S,j∈S,i=jmax​{maxlen(LCA(i,j))}。这就变成了一个纯树上数据结构问题。 离线询问，将询问按 rrr 排序。需要支持的操作是加入一个点，求后缀 max⁡\maxmax。可以看出我们打算在每个 iii 处维护所有 (i,j)(i,j)(i,j) ...

Statement 给定整数 n,an,an,a。 定义『好的珠子』由一个无序三元组 (x1,x2,x3)(x_1,x_2,x_3)(x1​,x2​,x3​) 表示，且满足 1≤xi≤a1\le x_i\le a1≤xi​≤a，gcd⁡{x1,x2,x3}=1\gcd\{x_1,x_2,x_3\}=1gcd{x1​,x2​,x3​}=1。 定义『好的项链』是一串由 nnn 个珠子构成的环，满足相邻两个珠子不同。 试统计本质不同（即循环不同构）的好的项链的个数，答案对 109+710^9+7109+7 取模。 TTT 组数据。数据范围：n≤1014n\le10^{14}n≤1014，a≤107a\le10^7a≤107，T≤10T\le10T≤10。时限 3 s3~\text{s}3 s。 Solution 二合一题。 统计好的珠子个数 考虑容斥。设 f(x)f(x)f(x) 表示 gcd=x\text{gcd}=xgcd=x 的无序三元组个数，g(x)g(x)g(x) 表示 gcd⁡\gcdgcd 为 xxx 的倍数的无序三元组个数。 显然有 g(d)=∑d∣nf(x)g(d) ...

Statement 给定长度为 nnn 的序列 aia_iai​，qqq 次询问，每次询问给定 l,rl,rl,r，求 a[l:r]a[l:r]a[l:r] 的所有非空子串的最小值之和。 数据范围：n,q≤105n,q\le10^5n,q≤105，∣ai∣≤109|a_i|\le10^9∣ai​∣≤109。 Solution 一个询问 l,rl,rl,r 的答案 ans(l,r)=ans(l,x−1)+ans(x+1,r)+ax⋅(x−l+1)⋅(r−x+1)\text{ans}(l,r)=\text{ans}(l,x-1)+\text{ans}(x+1,r)+a_x\cdot(x-l+1)\cdot(r-x+1)ans(l,r)=ans(l,x−1)+ans(x+1,r)+ax​⋅(x−l+1)⋅(r−x+1)。其中 xxx 是 l,rl,rl,r 中最小值元素的下标。 ans(l,x−1)\text{ans}(l,x-1)ans(l,x−1) 和 ans(x+1,r)\text{ans}(x+1,r)ans(x+1,r) 本质相同，现考虑求后者。 如果记 fi=[1,i]+[ ...