2020-2021:teams:farmer_john:2020暑假精选题目:数学
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020暑假精选题目:数学 [2020/12/24 20:03] jjleo |
2020-2021:teams:farmer_john:2020暑假精选题目:数学 [2020/12/24 20:07] (当前版本) jjleo [题解] |
||
|---|---|---|---|
| 行 11: | 行 11: | ||
| 给你一个长度为$n$的序列，问你有多少个子序列的$\gcd=1$，对$10^9+7$取模。$(n \le 10^5)$ | 给你一个长度为$n$的序列，问你有多少个子序列的$\gcd=1$，对$10^9+7$取模。$(n \le 10^5)$ | ||
| ====题解==== | ====题解==== | ||
| - | 本题我们需要求出$$f_i=\sum_{\gcd(a_{p_{1}},a_{p_{1}},\cdots,a_{p_{k}}) = i}1$$设$$cnt_i=\sum_{j=1}^n[i|a_j]$$则$$f_i=\sum_{j=1}^{cnt_i}\binom{cnt_i}{j}-\sum_{j=1}^nf_j[i|j]$$ $$=2^{cnt_i}-1-\sum_{j=1}^nf_j[i|j]$$ 逆序枚举$i$即可$O(n \log n)$求解。 | + | 本题我们需要求出$$f_i=\sum_{\gcd(a_{p_{1}},a_{p_{1}},\cdots,a_{p_{k}}) = i}1$$设$$cnt_i=\sum_{j=1}^n[i|a_j]$$则$$f_i=\sum_{j=1}^{cnt_i}\binom{cnt_i}{j}-\sum_{j=1}^Nf_j[i|j]$$ $$=2^{cnt_i}-1-\sum_{j=1}^Nf_j[i|j]$$ 逆序枚举$i$即可$O(n \log n)$求解。 |
| =====CF839D===== | =====CF839D===== | ||
| 行 17: | 行 17: | ||
| 给出一个长度为$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)$ | ||
| ====题解==== | ====题解==== | ||
| - | 上一题的升级版，我们在上一题我们通过容斥求出了$$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|j]$$ $$=\sum_{j=1}^{cnt_i}\frac{(cnt_i)!j}{j!(cnt_i-j)!}-\sum_{j=1}^ng_j[i|j]$$ $$=cnt_i\sum_{j=1}^{cnt_i}\frac{(cnt_i-1)!}{(j-1)!(cnt_i-j)!}-\sum_{j=1}^ng_j[i|j]$$ $$=cnt_i\sum_{j=0}^{cnt_i-1}\binom{cnt_i-1}{j}-\sum_{j=1}^ng_j[i|j]$$ $$=cnt_i \cdot 2^{cnt_i-1}-\sum_{j=1}^ng_j[i|j]$$ 逆序枚举$i$即可$O(n \log n)$求解。 | + | 上一题的升级版，我们在上一题我们通过容斥求出了$$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|j]$$ $$=\sum_{j=1}^{cnt_i}\frac{(cnt_i)!j}{j!(cnt_i-j)!}-\sum_{j=1}^Ng_j[i|j]$$ $$=cnt_i\sum_{j=1}^{cnt_i}\frac{(cnt_i-1)!}{(j-1)!(cnt_i-j)!}-\sum_{j=1}^Ng_j[i|j]$$ $$=cnt_i\sum_{j=0}^{cnt_i-1}\binom{cnt_i-1}{j}-\sum_{j=1}^Ng_j[i|j]$$ $$=cnt_i \cdot 2^{cnt_i-1}-\sum_{j=1}^Ng_j[i|j]$$ 逆序枚举$i$即可$O(n \log n)$求解。 |
2020-2021/teams/farmer_john/2020暑假精选题目/数学.1608811381.txt.gz · 最后更改: 2020/12/24 20:03 由 jjleo
