目录
CF Prefix Sums
题意
给出一个长度为$n$的序列，问多少次前缀和操作后序列最大值可以超过$k$，保证序列至少有两个数为正。$(2 \le n \le 2 \times 10^5, 1 \le k \le 10^{18})$
题解
由F题可知，前缀和操作的增长速度是$O(x^{n-1})$的，在$k=10^{18}$的数据范围下，只有$n=2,3$时暴力模拟复杂度过高，其它情况都可以直接暴力模拟。$n=2$时就是一直加一个数，可以直接算；$n=3$时就是一直加一个数和一个等差数列求和，解二次方程或二分都可以。（注意去掉所有前导$0$剩下的位数才是真正的$n$，因为前面的$0$无论多少次操作都不会变）
CF Winter is here
题意
给出一个长度为$n$的序列$a_i$，求$$\sum_{\gcd(a_{p_{1}},a_{p_{1}},\cdots,a_{p_{k}}) \ne 1}k \cdot \gcd(a_{p_{1}},a_{p_{1}},\cdots,a_{p_{k}}) \pmod{10^9+7}$$其中$1 \le k \le n, p_1<p_2< \cdots < p_k$。$(n \le 2 \times 10^5, a_i \le 10^6)$
题解
本题是Coprime Subsequences的升级版。在上一题我们通过容斥求出了$$f_i=\sum_{\gcd(a_{p_{1}},a_{p_{1}},\cdots,a_{p_{k}}) = i}1$$本题我们则需要求出$$g_i=\sum_{\gcd(a_{p_{1}},a_{p_{1}},\cdots,a_{p_{k}}) = i}k$$ 最终答案为 $$\sum_{i=2}^{n}ig_i$$ 类似上一题的方法设$$cnt_i=\sum_{j=1}^n[i|a_j]$$则$$g_i=\sum_{j=1}^{cnt_i}j\binom{cnt_i}{j}-\sum_{j=1}^ng_j[i|a_j]$$ $$=\sum_{j=1}^{cnt_i}\frac{(cnt_i)!j}{j!(cnt_i-j)!}-\sum_{j=1}^ng_j[i|a_j]$$ $$=cnt_i\sum_{j=1}^{cnt_i}\frac{(cnt_i-1)!}{(j-1)!(cnt_i-j)!}-\sum_{j=1}^ng_j[i|a_j]$$ $$=cnt_i\sum_{j=0}^{cnt_i-1}\binom{cnt_i-1}{j}-\sum_{j=1}^ng_j[i|a_j]$$ $$=cnt_i \cdot 2^{cnt_i-1}-\sum_{j=1}^ng_j[i|a_j]$$ 逆序枚举$i$即可$O(n \log n)$求解。
CF Convex Countour
题意
给出一个$n$个点的凸包，保证任意三点不共线。求一条仅由线段组成的路径，要求该路径恰好经过每个点一次且不自交。求符合条件路径长度的最大值。$(3 \le n \le 2500)$
题解
因为是凸包且要求不自交，所以一条路径在向外扩展的途中任意时刻一定都是覆盖一个连续的区间，否则如果不连续，再想回来覆盖中间的点就会导致自交。
