======数学======

=====CF803C=====
====题意====
请你构造一个长度为$k$的严格上升正整数序列，使得所有数的和恰好为$n$，并且所有数的最大公约数最大。输出这个序列。如果没有合法的序列输出$-1$。如果有多个合法的序列，可以输出任意一个。$(n,k \le 10^{10})$
====题解====
枚举$\gcd$，只要$\gcd \cdot \frac{k(k+1)}{2} \le n$即有解。

=====CF803F=====
====题意====
给你一个长度为$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)$求解。

=====CF839D=====
====题意====
给出一个长度为$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)$求解。


=====CF812E=====
====题意====
给出一棵$n$个节点的有根树，保证所有叶子节点到根节点路径的奇偶性相同，每个节点上有一些苹果，两人轮流操作，每次可以将一些苹果移动到它的一个儿子上，如果是叶子节点则直接删除这些苹果，最后无法操作的人输。问先手必胜还是必败。$(n \le 10^5)$
====题解====
可以发现距离叶子节点奇数长度的苹果都是无意义的，因为对方可以照搬你的操作从而将这些苹果删除，而距离叶子节点偶数长度的苹果可以通过一次转移到距离叶子节点奇数长度的节点，相当于将其“删除”。因此游戏转化为nim和游戏，所有距离叶子节点偶数长度的苹果数为一个石子堆。


=====CF809E=====

====题意====
给出一棵$n(2 \le n \le 2 \times 10^5)$个节点的树，边权为$1$。给定一个$1$到$n$的排列$a_i$，设$\operatorname{dist}(i,j)$为树上两点间距离，求$$\frac{1}{n(n-1)}\sum_{i=1}^{n}\sum_{j=1}^{n} \varphi(a_i \cdot a_j) \operatorname{dist}(i,j)\pmod{10^9+7}$$
====题解====
因为$a_i$是$1$到$n$的排列，所以我们可以设$p_{a_i}=i$。同时有以下结论$$\varphi(nm)=\frac{\varphi(n)\varphi(m)\gcd(n,m)}{\varphi(\gcd(n,m))}$$ 因此扔掉前面的分母$n(n-1)$，原式转化为$$\sum_{i=1}^{n}\sum_{j=1}^{n} \frac{\varphi(i)\varphi(j)\gcd(i,j)\operatorname{dist}(p_i, p_j)}{\varphi(\gcd(i,j))} $$ 开始反演，枚举$d=\gcd(i,j)$ $$=\sum_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{d} \right\rfloor} \varphi(id)\varphi(jd)\operatorname{dist}(p_{id}, p_{jd}) [\gcd(i,j)=1] $$ 套用$\epsilon = \mu * 1$ $$=\sum_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{i=1}^{\left\lfloor \frac{n}{d} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{d} \right\rfloor} \varphi(id)\varphi(jd)\operatorname{dist}(p_{id}, p_{jd}) \sum_{p|\gcd(i,j)}\mu(p)$$ 枚举$p$ $$=\sum_{d=1}^{n}\frac{d}{\varphi(d)}\sum_{p=1}^{\left\lfloor \frac{n}{d} \right\rfloor} \mu(p) \sum_{i=1}^{\left\lfloor \frac{n}{dp} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{dp} \right\rfloor} \varphi(idp)\varphi(jdp)\operatorname{dist}(p_{idp}, p_{jdp})$$ 枚举$T=dp$ $$=\sum_{T=1}^{n} \sum_{i=1}^{\left\lfloor \frac{n}{T} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{T} \right\rfloor} \varphi(iT)\varphi(jT)\operatorname{dist}(p_{iT}, p_{jT}) \sum_{d|T} \frac{\mu(\frac{T}{d})d}{\varphi(d)}$$ 设$$f(T)=\sum_{i=1}^{\left\lfloor \frac{n}{T} \right\rfloor}\sum_{j=1}^{\left\lfloor \frac{n}{T} \right\rfloor} \varphi(iT)\varphi(jT)\operatorname{dist}(p_{iT}, p_{jT})$$ $$g(T)=\sum_{d|T} \frac{\mu(\frac{T}{d})d}{\varphi(d)}$$ 则原式转化为$$\sum_{T=1}^{n}f(T)g(T)$$ 其中$g(T)$可以在$O(n \log n)$的时间求出，考虑$f(T)$，本质相当于给$p_i$点一个权值$\varphi(i)$，然后把所有下标为$T$的倍数点$p_i$拿出来建虚树，dp跑一遍将每条边的长度乘以两侧节点权值和即可，总结点数是$O(n \log n)$的，因此总复杂度为$O(n \log n)$。

=====CF1400G=====
====题意====
$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)$。