毒瘤数学题汇总（二）

· · 个人记录

上来先搞个链表

毒瘤数学题汇总

51nod 1355 斐波那契数列的最小公倍数

题意

输出Lcm(F(a1), F(a2) ...... F(an)) Mod 1000000007的结果。

n <= 50000, a <= 1000000

题解

ddy题解

首先要知道一个结论：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]旧试题

题意

求：

\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) 地建边了。

三元环科技见：不常用的黑科技——「三元环」

更多细节见题解代码。

P5400 [CTS2019]随机立方体

又是一道做了好几个月的题（其实是鸽了好几个月的题）

题目简短，代码简短，思维量极大。

首先看到“至少”，并且直接算还不好算，就应该想到二项式反演，变成“钦定”。

设 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) 了：

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：

n \\ k \end{pmatrix}\begin{pmatrix} m \\ k \end{pmatrix}\begin{pmatrix} l \\ k \end{pmatrix}k!k!k! 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 表示值域）。如果害怕过不去的话，可以使用求逆元小技巧：

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

感觉和 主旋律 的套路有些像。

又是竞赛图，根据套路，应该枚举缩点后最后一个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