A. CF1845E Boxes and Balls
\dzy/ 强大 \dzy/
注意到球之间的相对位置不会改变，设 x i x_i xi 为初始状态第 i i i 个球的位置， y i y_i yi 为末状态位置，那么移动的最少步数是 ∑ ∣ y i − x i ∣ \sum |y_i - x_i| ∑∣yi−xi∣，实际移动步数可能是 ∑ ∣ y i − x i ∣ \sum |y_i - x_i| ∑∣yi−xi∣ 加上一个偶数，即来回移动而不改变状态。
记 f ( i , j , s ) f(i,j,s) f(i,j,s) 表示前 i i i 个盒子，放了 j j j 个小球，前 i i i 个盒子 ∑ \sum ∑ 值为 s s s 的方案数，有 f ( i , j , s ) = f ( i − 1 , j , s ) + f ( i − 1 , j − 1 , s + ∣ i − a j ∣ ) f(i,j,s) = f(i-1,j,s) + f(i-1,j-1,s+|i-a_j|) f(i,j,s)=f(i−1,j,s)+f(i−1,j−1,s+∣i−aj∣)。
最后的答案为 ∑ f ( n , t o t , k ′ ) \sum f(n,tot,k') ∑f(n,tot,k′)， k ′ k' k′ 即为 k k k 减去一个偶数。
这样是 O ( n 2 k ) O(n^2k) O(n2k) ，空间可以滚掉一维，考虑时间优化。
记 s u m i sum_i sumi 表示初始状态前 i i i 个盒子中的小球数量。
在枚举 j j j 的时候，前 i i i 个盒子里放的小球数量和初始状态相差 ∣ s u m i − j ∣ |sum_i-j| ∣sumi−j∣ 个。以 s u m i > j sum_i>j sumi>j 为例，那么对于这些多出来的小球，就算移到后面几个最近的箱子，也需要 ( s u m i − j ) 2 (sum_i-j)^2 (sumi−j)2 步，因此枚举 j j j 的时候可以划小范围到一个 K \sqrt K K 级的范围。记录
B.CF1842G Tenzing and Random Operations
\wzr/ \wy/
确实顶，组合意义。
0 0 0 到 n n n 这 n + 1 n+1 n+1 个点， n n n 条路， i i i 条路有 a i a_i ai 种方案， ∏ a i \prod a_i ∏ai 就是到 n n n 的方案数。修改操作就是路上随机给一些工具，工具 两两不同，使用工具可以给你 v v v 种额外方案。
先不考虑期望，考虑方案数，最终的期望就是所有情况方案数之和除个 n m n^m nm。
设 d p i , j dp_{i,j} dpi,j 表示到第 i i i 个，使用了 j j j 个工具的方案数。
转移：
- 不使用工具： d p i − 1 , j × a i dp_{i-1,j} \times a_i dpi−1,j×ai。
- 使用用过的工具：使用的是哪一个有 j j j 种可能： d p i − 1 , j × j × v dp_{i-1,j} \times j \times v dpi−1,j×j×v。
- 使用没有用过的工具： 来的地方有 i i i 种可能，使用的是哪一个有 ( m − j + 1 ) (m-j+1) (m−j+1) 种可能： d p i − 1 , j − 1 × i × ( m − j + 1 ) × v dp_{i-1,j-1} \times i \times (m-j+1) \times v dpi−1,j−1×i×(m−j+1)×v。
对于 d p i , j dp_{i,j} dpi,j 在计算总方案数时记得考虑 m − j m - j m−j 个没使用的工具的可能性，即 ∑ j = 0 min ( n , m ) ( d p n , j × n m − j ) \sum\limits_{j=0}^{\min(n,m)} {(dp_{n,j} \times n^{m-j})} j=0∑min(n,m)(dpn,j×nm−j)，乘上 1 n m \frac {1} {n^m} nm1 就是期望。记录
C. CF1838E Count Supersequences
给定了都是 [ 1 , k ] [1,k] [1,k] 之间的数，从匹配的角度，只有匹配与不匹配，也就是 1 1 1 与 k − 1 k-1 k−1 ，与 a a a 具体无关。
反着做，考虑只能匹配 i i i 位的方案数 f i f_i fi，首先确定每一位第一次匹配到的位置，因为是第一次， [ i , i + 1 ) [i,i+1) [i,i+1) 之间就不能和 a i + 1 a_{i+1} ai+1 相同，每一个 i , i + 1 i,i+1 i,i+1 段都是这样，因此 f i = ( m i ) ( k − 1 ) m − i f_i = \dbinom {m}{i}{(k-1)}^{m-i} fi=(im)(k−1)m−i，答案就是 ∑ i = 0 n f i \sum\limits_{i=0}^n f_i i=0∑nfi。注意到组合数只用求 m m m 取 i i i ，可以递推。注意取模。记录
D. CF1843E MEX of LCM
I. 第 n + 1 n+1 n+1 个质数一定可以作为答案，因此答案一定小于这个数。因此答案值域有上界 V ≈ 4.5 × 1 0 6 V\approx4.5 \times 10^6 V≈4.5×106 。
II. 固定左端点，移动右端点，若 lcm 变化则至少变两倍，因此固定左端点至多 log V \log V logV 种，可以倍增 log n \log n logn 找出来第一个发生变化的 lcm。
III. 对于区间 lcm ，可以 st 表预处理。
枚举左端点，二分找下一个 lcm 变化点，时间复杂度 O ( n log n log V ) O(n \log n \log V) O(nlognlogV)。这种做法一开始一直 TLE on 25，后来加特判才过。记录
发现这样做本质还是为了 lcm 不重复出现，想到 STL 里面的 set，这样的 set 元素至多 log V \log V logV 个。从右往左枚举左端点 l l l（或者从左往右枚举右端点），维护区间左端点为 l l l 的集合，可以通过 l + 1 l+1 l+1 的集合元素与 a l a_l al 做 lcm 得到。记录文章来源：https://www.toymoban.com/news/detail-560875.html
E. CF1830C Hyperregular Bracket Strings
满足区间性质的是个卡特兰数，然后拆区间哈希什么的，不想搞了。文章来源地址https://www.toymoban.com/news/detail-560875.html
到了这里，关于Day 3 Math的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
