目录
- 「CF1726E」Almost Perfect
- 「CF95E」Lucky Country
- 「CF1245F」Daniel and Spring Cleaning
- 「CF1372E」Omkar and Last Floor
- 「AGC038C」LCMs / 「LG-P3911」最小公倍数之和
「CF1726E」Almost Perfect
观察发现，排列中只会含有一元置换环，二元置换环，类似 \((j,j+1,i,i+1)\) 的四元置换环。
具体证明忽略，接下来考虑咋做。
首先忽略四元环，容易推出只有一元环和二元环的式子：\(f_i=f_{i-1}+(i-1)f_{i-2}\)。
枚举四元环个数 \(i\)，则选出四元环的方案数为 \(\binom{n-2i}{2i}\frac{(2i)!}{i!}\)，解释就是先选出不相邻的数，再将他们组成 \((i,j)\) 这样的二元组，再乘上其他方案即可。
「CF95E」Lucky Country
乐子题，使用并查集求出连通块大小之后，问题就变成一个多重背包问题。
注意到物品的体积总和固定，那么本质不同的物品个数也就 \(\sqrt{n}\) 种，直接二进制分组即可。
「CF1245F」Daniel and Spring Cleaning
乐子题 *2。考虑二进制位，异或被称为不进位加法，那说明进位就寄，问题也就变成了：
\[\sum_{a=l}^r\sum_{b=l}^r [a\And b=0] \]容斥后，数位 DP 即可。
「CF1372E」Omkar and Last Floor
状态挺难猜到的。
设 \(f_{l,r}\) 表示 \([l,r]\) 这之中的列的贡献。
考虑枚举某一列 \(k\)，将经过 \(k\) 的全部填上 \(1\)，然后左右两边 \(f_{l,k-1}\) 和 \(f_{k+1,r}\) 是子问题，可以直接递归下去做。
由此可以简单做到 \(O(n^4)\)，据说可以做到 \(O(n^3)\)。
「AGC038C」LCMs / 「LG-P3911」最小公倍数之和
两者本质相同，我们以后者为例进行讨论。
设 \(x\) 出现了 \(c_x\) 次，可以将式子改写成：
\[\begin{aligned} & \sum_{i=1}^n\sum_{j=1}^n \text{lcm}(i,j)c_ic_j\\ = & \sum^n_{i=1}\sum^n_{j=1} \frac{ijc_ic_j}{\gcd(i,j)}\\ = & \sum_{d=1}^n\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}[\gcd(i,j)=1]ijdc_{id}c_{jd}\\ = & \sum_{d=1}^n\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}\sum_{t|i,t|j}\mu(t)ijdc_{id}c_{jd}\\ = & \sum_{d=1}^n\sum_{t=1}^{n/d}\sum_{i=1}^{n/dt}\sum_{j=1}^{n/dt}\mu(t)ijt^2dc_{itd}c_{jtd}\\ = & \sum_{T=1}^nT(\sum_{i=1}^{n/T}ic_{iT})^2\sum_{t|T}\mu(t)t \end{aligned} \]预处理后面的 \(\sum_{i|T}\mu(t)t\) 即可做到 \(O(n\ln n)\)。
标签：四元,Set,公倍数,题解,sum,mu,ic,杂题,2i From： https://www.cnblogs.com/cnyzz/p/16791725.html