2020-2021:teams:farmer_john:2020.8.18
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020.8.18 [2020/08/19 23:37] jjleo [题解] |
2020-2021:teams:farmer_john:2020.8.18 [2020/08/20 12:30] (当前版本) jjleo [CF] |
||
|---|---|---|---|
| 行 10: | 行 10: | ||
| 给出一个长度为$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)$ | 给出一个长度为$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)$ | ||
| ====题解==== | ====题解==== | ||
| - | 本题是[[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$$类似上一题的方法，设$$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]$$ | + | 本题是[[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)$ | ||
| ====题解==== | ====题解==== | ||
| + | 因为是凸包且要求不自交，所以一条路径在向外扩展的途中任意时刻一定都是覆盖一个连续的区间，否则如果不连续，再想回来覆盖中间的点就会导致自交。 | ||
| =====CF ===== | =====CF ===== | ||
| ====题意==== | ====题意==== | ||
2020-2021/teams/farmer_john/2020.8.18.1597851477.txt.gz · 最后更改: 2020/08/19 23:37 由 jjleo
