毒瘤数学题汇总（二）

~~上来先搞个链表~~ # [毒瘤数学题汇总](https://www.luogu.com.cn/blog/jzp1115/du-liu-shuo-xue-ti-hui-zong) ## [51nod 1355 斐波那契数列的最小公倍数](http://www.51nod.com/Challenge/Problem.html#problemId=1355) ### 题意 输出Lcm(F(a1), F(a2) ...... F(an)) Mod 1000000007的结果。 n <= 50000, a <= 1000000 ### 题解 [ddy题解](https://www.luogu.com.cn/blog/nofind/post-51nod-1355-fei-bo-nei-qie-di-zui-xiao-gong-bei-shuo-min-max-rong-post) 首先要知道一个结论：$gcd(f[i], f[j]) = f[gcd(i, j)]$，其中 $f$ 为斐波那契数列。 题目的意思是说，求： $$LCM_{i∈S}f[i]$$ 质因数分解得： $$\prod_{p}p^{max_{i∈S}(b_i)}$$ 然而我们只知道gcd相关，因此将其用min-max定理尝试转化成gcd: $$\prod_p p^{\sum_{T∈S,T\not=0}min_{i∈T}(b_i)(-1)^{|T| + 1}}$$ 将关于一个 $T$ 的所有子集的$p$合并一下： $$\prod_{T∈S,T\not=0}gcd_{i∈T}(f[i])^{(-1)^{|T| + 1}}$$ 套用上面的那个结论： $$\prod_{T∈S,T\not=0}f[gcd_{i∈T}(i)]^{(-1)^{|T| + 1}}$$ 再套用经典版的莫比乌斯反演，众所周知： $$f(n)=\sum_{i|n}g(i)$$ $$g(n)=\sum_{i|n}f(i)\mu(i)$$ 其实对于连乘积也有类似的式子： $$f(n) = \prod_{i|n}g(i)$$ $$g(n)=\prod_{i|n}f(i)^{\mu(i)}$$ 两式两边都取对数即可证明。 那么我们将 $f[gcd(T)]$ 看作 $f(n)$，这样的话 $f[gcd(T)]$ 会略微好看一些。同时 $g(n)$ 也可以在 $O(nlnn)$ 的时间内搞定。 那么我们继续推式子: $$\prod_{T∈S,T\not=0} \prod_{d|gcd(T)} g(d)^ {(-1)^{|T| + 1}}$$ 然后提取 $g(d)$： $$\prod_d g(d)^{\sum_{T,T\not=0,d|gcd(T)}(-1)^{|T| + 1}}$$ 发现其中的 $d|gcd(T)$ 很有意思，它的意思是 $d$ 能够整除 $T$ 中的所有数。那么我们只用在 $S$ 中仅选择一些 $d$ 的倍数组成 $T$，就可以让 $g(d)$ 做出贡献：（假设 $S$ 中有 $cnt$ 个数是 $d$ 的倍数） $$\sum_{i>0} C_{cnt}^{i}(-1)^{|i|+1}$$ 这不就是二项式定理（组合恒等式)吗？只不过少了个 $i=0$。因此它等于： $$1$$ 也就是说，只要 $S$ 中含有 $d$ 的倍数，就会有一个 $g(d)$ $$\prod_d g(d)$$ 然后$O(nlnn)$预处理出 $g(d)$ 和 $d$，对应相乘即可。 Continued... ## [P4619 [SDOI2018]旧试题](https://www.luogu.com.cn/problem/P4619) ### 题意 求： $$\sum_{i=1}^A \sum_{j=1}^B \sum_{k=1}^C d(ijk)$$ 其中 $d(n)$ 表示 $n$ 的约数个数。 $$A,B,C<=100000$$ ### 题解 首先如果 $C=0$，那么就成了一个经典的数论问题： $$\sum_{i=1}^A\sum_{j=1}^B d(ij)$$ 可以转化为： $$\sum_{i=1}^A \sum_{j=1}^B \sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$$ **这就相当于枚举 $\frac{i}{x} * y$，并且能够恰好不重不漏地枚举到所有约数。可以质因数分解后理解。** 那么对于 $C > 1$ 的情况，是否存在类似的枚举方法呢？ 实际上是有的。 $$\sum_{i=1}^A \sum_{j=1}^B \sum_{k=1}^C d(ijk)$$ 可以转化为： $$\sum_{i=1}^A \sum_{j=1}^B \sum_{k=1}^C \sum_{x|i} \sum_{y|j} \sum_{z|k}[(x,y)=1][(y,z)=1][(x,z)=1]$$ 交换求和号：（这一步还是比较重要的，否则会带着九个$\sum$ 走向自闭） $$\sum_{x=1}^A \sum_{y=1}^A \sum_{z=1}^A [(x,y)=1][(y,z)=1][(x,z)=1] (\frac{A}{x})(\frac{B}{y})(\frac{C}{z})$$ 我们看到了亲切的中括号，自然地想到莫比乌斯反演。 $$\sum_{x|i} \sum_{y|j} \sum_{z|k} (\frac{A}{x})(\frac{B}{y})(\frac{C}{z}) \sum_{u|x,u|y} \sum_{v|y,v|z} \sum_{w|x,w|z} \mu(u)\mu(v)\mu(w)$$ 然后很自然地想到提前 $\mu$。不过平时都是只提前一个，这次一下子提前了三个，实际上**只要保证每一个 $\mu$ 被枚举的次数是一样的，那么这个转化就是可以的。** 假设 $A > B > C$。 $$\sum_{u=1}^A \sum_{v=1}^A \sum_{w=1}^A \mu(u)\mu(v)\mu(w) \sum_{u|x,w|x} \sum_{u|y,v|y} \sum_{v|z,w|z} (\frac{A}{x})(\frac{B}{y})(\frac{C}{z})$$ 略微再换一下顺序: $$\sum_{u=1}^A \mu(u) \sum_{v=1}^A \mu(v) \sum_{w=1}^A \mu(w) \sum_{u|x,w|x} (\frac{A}{x}) \sum_{u|y,v|y} (\frac{B}{y}) \sum_{v|z,w|z} (\frac{C}{z})$$ 其中$u|x,w|x$太麻烦，不过它等同于 $[u,w]|x$。因此: $$\sum_{u=1}^A \mu(u) \sum_{v=1}^A \mu(v) \sum_{w=1}^A \mu(w) \sum_{[u,w]|x} (\frac{A}{x}) \sum_{[u,v]|y} (\frac{B}{y}) \sum_{[v,w]|z} (\frac{C}{z})$$ 发现右面结构比较相似，用一个函数总结一下： $$f_T(n) = \sum_{n|x}(\frac{T}{x})$$ 这样就成了： $$\sum_{u=1}^A \mu(u) \sum_{v=1}^A \mu(v) \sum_{w=1}^A \mu(w) f_A([u,w])f_B([u,v])f_C([v,w])$$ ~~然后就可以 $O(n^3)$ 枚举了。~~ 发现还是 $n^3$。不过这次我们就不用枚举完$n^3$，因为最小公倍数通常会是 $n^2$ 级别，$f_T(n)$ 通常是0，那么如果它是0的话我们就不用管他了。 然而其中的 $n$ 其实是个数对的最小公倍数，一下子限制两个数。一组非零的解为 $u,v,w,\mu()\not=0,[...]<=A$，符合这个的有序三元组 $(u,v,w)$ 可以有贡献。那么我们只用枚举这些三元组即可。如果我们将符合条件的数对连接，那么实际上我们是在枚举一些三元环。 实测表示，图中的边并不多，枚举所有三元环的复杂度为 $O(m \sqrt m)$。因此，如果我们能够迅速连边，迅速枚举三元环的话，就可以通过这道题了。 建边的话，首先我们可以枚举所有的lcm，当然要抛弃掉 $\mu$ 为0的。那么剩下的应该不会一个质因数出现超过一次。那么我们将其质因数分解，然后要从中选取两个数，使得其Lcm为我们枚举的那个lcm。这一部分可以枚举子集 和 子集的子集+补集来实现。这样我们就可以近似 $O(m)$ 地建边了。 三元环科技见：[不常用的黑科技——「三元环」](https://www.luogu.com.cn/blog/KingSann/fou-chang-yong-di-hei-ke-ji-san-yuan-huan-post) 更多细节见题解代码。 ## [P5400 [CTS2019]随机立方体](https://www.luogu.com.cn/problem/P5400) 又是一道做了好几个月的题（其实是鸽了好几个月的题） 题目简短，代码简短，思维量极大。 首先看到“至少”，并且直接算还不好算，就应该想到二项式反演，变成“钦定”。 设 $f(k)$ 表示**钦定** $k$ 个“极值点”（极大格子，简称“极值”或“极点”）的方案数。“钦定”即我们只考虑与之相关的东西即可，即每个点能控制其控制区间（即同行或同列或同层），且不相互控制。 设 $h(i)$ 表示将 $i$ 个极点及其管辖区域（同控制区间)从小到大一点一点分配好数字（只考虑相对大小，不考虑真实的值）的方案数。 设 $g(i)$ 表示 $i$ 个极值点的管辖区域大小。这个最好算，是 $tot - (n - i)(m-i)(l-i)$，其中 $tot = n * m * l$。 然后就可以用 $h(k)$ 和 $g(k)$ 来表示 $f(k)$ 了： $$f(k) = \begin{pmatrix} tot \\ g(k) \end{pmatrix}(tot - g(k))!h(k)\begin{pmatrix} n \\ k \end{pmatrix}\begin{pmatrix} m \\ k \end{pmatrix}\begin{pmatrix} l \\ k \end{pmatrix}k!k!k!$$ （先从 $tot$ 个数里面选择 $g(k)$ 个数作为我们管辖区域的数集，管辖区域外面的数随便选；再选出极点的位置（用有序三元组表示，**相对顺序为大小顺序，因此共三个阶乘**），最后从小到大一点点算 $h(k)$） 现在考虑推 $h(i)$。我们重新分配数字，由于之前乘了阶乘，使三元组有序，因此我们已经知道最大的是那一个点了。最大的数字一定被分配给**第** $i$ 个极点，剩下的**由 $i$ 多管辖的那部分点** （共 $g(i) - g(i-1) - 1$ 个点）依次**随便**选数，剩下的顺序交给 $h(i-i)$ 处理。即： $$h(i) = (g(i)-1)(g(i)-2)...(g(i - 1) + 1)h(i-1)$$ 阶乘的形式表示： $$h(i) = \frac{(g(i)-1)!}{g(i-1)!}h(i-1)$$ 根据 $h(0) = 1$ 以及 $g(0) = 1$，展开 $h$ ~~进行套娃~~ $$h(i) = \frac{(g(i)-1)!}{g(i-i)!} \frac{(g(i-1)-1)!}{g(i-2)!}...\frac{(g(1)-1)!}{1}$$ $$ = \frac{(g(i)-1)!}{g(i-1)g(i-2)...g(1)}$$ 化简 $f$： $$f(k) = \frac{tot!}{g(k)!}h(k)\begin{pmatrix} n \\ k \end{pmatrix}\begin{pmatrix} m \\ k \end{pmatrix}\begin{pmatrix} l \\ k \end{pmatrix}k!k!k!$$ $$f(k) = \frac{tot!}{g(k)g(k-1)...g(1)}\begin{pmatrix} n \\ k \end{pmatrix}\begin{pmatrix} m \\ k \end{pmatrix}\begin{pmatrix} l \\ k \end{pmatrix}k!k!k!$$ 再回过头来看二项式反演，设 $A(k)$ 表示**恰好**有 $k$ 个极点的方案数。 $$f(k) = \sum_{i=k}^{tot} \binom{tot}{i}A(i)$$ $$A(k) = \sum_{i=k}^{tot} (-1)^{i-k} \binom{tot}{i}f(i)$$ 设 $Ans(k)$ 表示**恰好**有 $k$ 个极点的概率。 $$Ans(k) = A(k) / (tot!)$$ $$= \sum_{i=k}^{tot} (-1)^{i-k} \binom{tot}{i}\frac{\binom{n}{i} \binom{m}{i} \binom{l}{i}i!i!i!}{g(1)g(2)...g(i)}$$ 发现这玩意可以算得挺快，那个 $1/(g(1)g(2)...g(i))$ 可以直接预处理出来，这样就能做到 $O(TnlogN)$（$N$ 表示值域）。如果害怕过不去的话，可以使用求逆元小技巧： ```cpp mul[0] = 1; for (register int i = 1; i <= mn; ++i) g[i] = ((tot - (n - i) * (m - i) % P * (l - i) % P) % P + P) % P, mul[i] = g[i] * mul[i - 1] % P; muli[mn] = quickpow(mul[mn], P - 2); for (register int i = mn - 1; i; --i) muli[i] = muli[i + 1] * g[i + 1] % P; ``` 这样就是 $O(Tn)$ 了。 ## [CF913F Strongly Connected Tournament](https://www.luogu.com.cn/problem/CF913F) 感觉和 [主旋律](https://darkbzoj.tk/problem/3812) 的套路有些像。 又是竞赛图，根据套路，应该枚举缩点后最后一个SCC。那么我们首先要知道 $i$ 个点变成 SCC 的概率，设为 $f_i$。发现需要容斥，套路仍然是枚举缩点后最后一个SCC。最后一个SCC的每个点一定被其余SCC中的所有点连，于是设辅助数组 $dp_{i,j}$ 表示$i$ 个点中最后一个SCC大小为 $j$，最后一个SCC内外边的概率积之和，根据 $dp_{i,j}$ 可以算出 $f_i$。 考虑如何算出 $dp_{i,j}$： $$dp_{i,0}=1$$ $$dp_{i,j}=dp_{i-1,j-1}p^{i-j}+dp_{i-1,j}(1-p)^j$$ 我们从小到大加入点，分别讨论点加到最后一个SCC还是其余SCC的情况可以此式。 然后考虑如何算出 $f_i$： $$f_1=1$$ $$\sum_{j=1}^idp_{i,j}f_i=1$$ 考虑 $i$ 个点的完全图的最后一个SCC的大小的所有情况的概率，它们的和应该是1. 现在我们回归原问题：计算 $i$ 个点完全定向所需的比赛的期望次数，设为 $g_i$，我们可以枚举一轮定向后产生各种最后SCC的情况，但是最终SCC可以看作子问题，而其余点并不能看作子问题，因为这个时候已经定好向了，不能再把第一次定向的贡献算上了，于是我们单独开一个辅助数组 $h_i$ 表示已经定好一次向的 $i$ 个点到完全定向的期望次数，那么有： $$g_1 = 0,g_2 = 1,h_1=h_2=0$$ $$g_n = {n \choose 2} + f_ng_n + \sum_{j=1}^{n-1}f_jdp_{n,j}(g_j+h_{n-j})$$ $$h_n = f_ng_n + \sum_{j=1}^{n-1}f_jdp_{n,j}(g_j+h_{n-j})$$ 最终答案即为 $g_n$