2020-2021:teams:farmer_john:2020暑假精选题目:数学
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020暑假精选题目:数学 [2020/09/04 15:47] 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|a_j]$$ $$=2^{cnt_i}-1-\sum_{j=1}^nf_j[i|a_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|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)$求解。 | + | 上一题的升级版，我们在上一题我们通过容斥求出了$$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)$求解。 |
| 行 38: | 行 38: | ||
| $n$个人，选出一个非空子集，第$i$个人要求如果他被选出来那么子集的大小必须在$[l_i,r_i]$，同时有$m$个限制，形如第$a_i$个人和第$b_i$个人不能同时被选，问合法的选择方案数量，对$998244353$取模。$(1 \le n \le 3 \cdot 10^5, 0 \le m \le \min(20, \dfrac{n(n-1)}{2}))$ | $n$个人，选出一个非空子集，第$i$个人要求如果他被选出来那么子集的大小必须在$[l_i,r_i]$，同时有$m$个限制，形如第$a_i$个人和第$b_i$个人不能同时被选，问合法的选择方案数量，对$998244353$取模。$(1 \le n \le 3 \cdot 10^5, 0 \le m \le \min(20, \dfrac{n(n-1)}{2}))$ | ||
| ====题解==== | ====题解==== | ||
| + | 如果没有第二个限制，只需要对所有区间差分一下然后枚举人数就完成了。因此我们考虑使用容斥进行计算违反了第二个限制的方案并将其减去。设$f_{S}$为至少包含状态$S$中的矛盾的方案数，其中$S$是一个二进制数，最终答案即为$$\sum_{S=0}^{2^m-1}(-1)^{\operatorname{popcount}(S)}f_S$$我们设不考虑第二个限制，允许自己所在队伍有$i$个人的数量为$c_i$；状态为$S$时所包含的人数为$cnt_S$，他们的区间交集为$[L_S,R_S]$那么有$$f_S=\sum_{i=L_S}^{R_S}\binom{n-cnt_S}{i}$$其中$cnt_S$不超过$2$m，因此我们在$O(nm)$的时间内预处理出$$g_{i,j}=\binom{n-i}{j}$$的前缀和，从而$O(1)$得到$f_S$。最后用总方案数减去不合法方案数即可，总时间复杂度为$O(nm+m2^m)$。 | ||
2020-2021/teams/farmer_john/2020暑假精选题目/数学.1599205630.txt.gz · 最后更改: 2020/09/04 15:47 由 jjleo
