2020-2021:teams:farmer_john:2020.8.18
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020.8.18 [2020/08/20 12:23] jjleo [题意] |
2020-2021:teams:farmer_john:2020.8.18 [2020/08/20 12:30] (当前版本) jjleo [CF] |
||
|---|---|---|---|
| 行 11: | 行 11: | ||
| ====题解==== | ====题解==== | ||
| 本题是[[2020.7.27|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)$求解。 | 本题是[[2020.7.27|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 ===== | + | =====CF Convex Countour===== |
| ====题意==== | ====题意==== | ||
| - | 给出一个$n$个点的凸包，保证任意三点不共线，求一组连续的折线段，使得每个顶点恰好经过一次，且任意两条不同的线段只在顶点处相交，求满足上述条件的总长度最大值$(3 \le n \le 2500)$ | + | 给出一个$n$个点的凸包，保证任意三点不共线。求一条仅由线段组成的路径，要求该路径恰好经过每个点一次且不自交。求符合条件路径长度的最大值。$(3 \le n \le 2500)$ |
| ====题解==== | ====题解==== | ||
| - | 因为是凸包且要求仅在顶点处相交，因此 | + | 因为是凸包且要求不自交，所以一条路径在向外扩展的途中任意时刻一定都是覆盖一个连续的区间，否则如果不连续，再想回来覆盖中间的点就会导致自交。 |
| =====CF ===== | =====CF ===== | ||
| ====题意==== | ====题意==== | ||
2020-2021/teams/farmer_john/2020.8.18.1597897422.txt.gz · 最后更改: 2020/08/20 12:23 由 jjleo
