毒瘤数学题汇总

· · 个人记录

2020.3.19 写此文以挽救我的可怜的数学 写此文以试图找出数学题的规律 （可能我又在瞎做梦呢）

毒瘤数学题汇总（二）

P3978 [TJOI2015]概率论

题意：

对于一棵随机生成的n个结点的有根二叉树(所有互相不同构的形态等概率出现),它的叶子节点数的期望是多少呢?

n <= 1e9$, 精度要求 $1e-9

题解

黑题？一看就像是个结论题。考虑打表解决。

先写个暴力：

//f[i]:i节点数的所有形态的叶子总和
//g[i]:i节点数的所有形态数
f[1] = 1; g[1] = 1; g[0] = 1;
for (register int i = 2; i <= n; ++i) {
    for (register int j = 0; j < i; ++j) {
        f[i] += f[j] * g[i - 1 - j] + f[i - 1 - j] * g[j];
        g[i] += g[j] * g[i - 1 - j];
    }
}

看起来 f 数组很奇怪，但是 g 数组很友善。

他是分治fft!

他有点像二项式反演！

分治fft 肯定没戏（因为我不会），二项式反演我也忘记了。但是记得似乎和组合数有关。

打表：

f[1] = 1, g[1] = 1

f[2] = 2, g[2] = 2

f[3] = 6, g[3] = 5

f[4] = 20, g[4] = 14

f[5] = 70, g[5] = 42

f[6] = 252, g[6] = 132

f[7] = 924, g[7] = 429

再打出杨辉三角：

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

1 8 28 56 70 56 28 8 1

1 9 36 84 126 126 84 36 9 1

1 10 45 120 210 252 210 120 45 10 1

1 11 55 165 330 462 462 330 165 55 11 1

1 12 66 220 495 792 924 792 495 220 66 12 1

（当然手写的杨辉三角更容易找到规律）

由此找到 f 的规律。

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

1 8 28 56 70 56 28 8 1

1 9 36 84 126 126 84 36 9 1

1 10 45 120 210 252 210 120 45 10 1

1 11 55 165 330 462 462 330 165 55 11 1

1 12 66 220 495 792 924 792 495 220 66 12 1

（这个规律更是得手动打出杨辉三角）

总结：

f[i] = C_{2 * (i - 1)}^{i - 1} g[i] = C_{2 * i - 1}^{i - 1} - C_{2 * i - 1}^{i - 2}

然后 g[i] 的式子有点像推卡特兰数时的式子，记得这两个组合数相减可以合并，于是大力合并得：

g[i] = \frac{C_{2 * i}^{i - 1}}{i}

然后觉得两个相似的组合数相除一定很有意思，于是再一次暴力把组合数拆成阶乘形式，相除得：

\frac{f[i]}{g[i]} = \frac{i * (i + 1)}{2 * (2 * i- 1)}

然后自以为得到了正确结果，特地开了 long ~ double，高高兴兴地交了上去。

结果纪中OJ 卡long ~ double，却不卡 double。然后就丢掉了20pts

然后还是失去了 做出第一道自己做出来的省选数学题 的机会。不过洛谷的 SPJ 是可以过的，也不算失败得那么彻底。

另：本题正解有关生成函数，卡特兰数，导数，拉格朗日反演等等，本人实在不会。

P3263 [JLOI2015]有意义的字符串

题意：

输入非负整数 b, d, n，求：

floor((\frac{b + \sqrt{d}}{2})^n)~ ~ mod ~ ~ P

其中 floor(x) 表示对 x 下取整（不超过 x 的最大整数），P = 7528443412579576937, n <= 1e18, 0 < b^2 <= d < (b + 1)^2 <= 1e18, b~mod~2 = 1, d~mod~4 = 1

部分分：

40pts: b < 100, n < 6 other ~ 20pts : b = 1,d = 5

题解

题目看起来有点怪？P 超级大（ 7e18），并且还不是质数；限制这么严：0 < b^2 <= d < (b + 1)^2 <= 1e18，并且b~mod~2 = 1, d~mod~4 = 1？似乎这些就是所谓“有意义的字符串”？

有什么意义？

首先，我们发现我们可以直接暴力来骗取大量分数 （考试时没理解题只有5分）。但是发现那个值在快速幂的时候会越来越大，越来越大，最终爆掉一切浮点数。怎么办？

如果求的是 floor((\frac{b - \sqrt{d}}{2})^n) 就好了，毕竟 \frac{b - \sqrt{d}}{2} 本来就是个绝对值小于1 的小数，再乘方 n 次，肯定越来越小。

然而题目求的并不是那个。但是我们可以利用那个。

考虑到 20pts 有点像黄金分割比，然后就想黄金分割比的推导过程是列方程。有 x_1 + x_2 = -\frac{b}{a}, x_1 * x_2 = \frac{c}{a}，就是说 A = \frac{1 - \sqrt{5}}{2}，B = \frac{1 + \sqrt{5}}{2}，就有 A + B = 1, A * B = -1。

其它情况有没有类似性质呢？

A + B = b, A * B = \frac{b^2 - d}{4}

然后根据题目的限制， A * B 正好是整数？这提示我们什么？

这提示我们找对了一条方向。

由于加上 (\frac{b - \sqrt{d}}{2})^n 对答案的影响不大（最多1），我们设 A = \frac{b + \sqrt{d}}{2}，B = \frac{b - \sqrt{d}}{2}，然后转而求 A^n + B^n。

由于 A, B 的信息非常丑陋，但是 A + B, A * B 的信息却十分美丽。我们尝试用 A + B, A * B 来表示 A^n + B^n。 似乎不太可。DP试试？我们尝试用 A + B, A * B 来推出 A^n, B^n。

设 f[n] = A^n + B^n。有递推式：

f[n + 1] = A^(n + 1) + B(n + 1) = (A^n + B^n) * (A + B) - A * B^n - B * A^n =(A^n + B^n) * (A + B) - A * B * (A^{n - 1} + B^{n - 1}) =f[n] * (A + B) - f[n - 1] * (A * B)

然后大力递推即可。

然后矩乘即可。

CF1327E Count The Blocks

题意：

给定正整数 n。

对于一个数 t，定义一个块是 t 中的连续相等的一串数字。

写下 0 ~ 10^n - 1 的所有数，不足 n 位的用前导 0 补足 n 位。

对于每个 i=1 ~ n，求这 10^n 个数中一共有多少个长为 i 的块。

题解：

（实际上也没有那么毒瘤）

一开始还想数位dp，但想着想着思路就跑到打表那里去了。因为它的答案实在太有规律了！

首先看样例：1 -> 10; 2 -> 180, 10

n = 2 时的第二个数竟然和 n = 1 时的第一个数相同？巧合？

手动（暴力）枚举的时候，发现：

n = 1 时一共有 1 * 10 个块

n = 2 时一共有 1 10 个“2”块， $200 - 2 10 = 180$ 个"1"块。

n = 3 时一共有 1 10 个“3”块， $200 - 2 10 = 180 个“2”块， 3000 - 3 10 - 2 90 = 2610$ 个“1”块。

n = 4 时似乎有特殊情况（一个数里面有两个“2”块），怎么办？规律会不会错？经验算，竟然和规律一样！

然后就坚信规律的正确性了。

规律：10, 200 - 2 * 10, 3000 - 3 * 10 - 2 * (200 - 2 * 10)...

然后我构造了一个 f[i] = i + 1 ，然后跑分治fft，然后 TLE 了。

实际上 f[i] = i + 1 这个数组实在太特殊了，特殊到根本不需要那么多高级数学操作！我们可以利用类似dp一样的东西来维护一些事情（前缀和）。

总之别老是想那么复杂的东西。

my record

CF1327D Infinite Path

题意：

给一个排列 p_i 和颜色数组 c_i。

定义一条“无限路径”为：i, p[i], p[p[i]], ...，并且要求路径上的颜色必须相同（c[i] = c[p[i]] = c[p[p[i]]]...）

定义排列的乘法：c = a * b -> c[i] = a[b[i]]，并依据次定义排列的乘方运算：p^k = p * p * p * ... * p（k 个 p）

询问最小的 k 使得 p^k 存在至少一条“无限路径”。

\sum n <= 1e5

题解：

题解 CF1327D 【Infinite Path】

神仙置换题

置换基础题。

发现排列的 p[p[p[p[p[...]]]]]] 有一点环的意思。我们这样建图(置换的套路）：i -> p[i]。 p^k表示每次走k 步所产生的图。发现原图会产生一些环，并且 p^k 所形成的图中环一定时原图的环分裂形成的，也就是说，环与环之间是相互独立的。因此我们对每一个环查找最小的 k，最终取全局最小即可。

然后暴力枚举每一个 k 复杂度大概是 O(n^2)。根据置换的某些知识，我们知道每次走 k 步形成的环其实和每次走 gcd(circle's ~siz, k) 步所形成的环是一样的。（估计真正考试的时候只能猜测+自信来得出这一结论了）因此真正有用的 k 一定是 circle's ~ siz 的约数。复杂度降至 O(nlogn)。

为了做到这样的复杂度，我们要有一定的代码实现能力。具体实现方法为：对于每一个环，我们先按顺序存到一个数组里面(0...circle's ~siz - 1)。然后在 che() 函数中的“走 k 步”就能够 O(1) 实现了。

my record

双倍经验：P6187 [NOI Online 提高组]最小环

P1447 [NOI2010]能量采集

题意：

求\sum_{i = 1}^{n} \sum_{j = 1}^{m} gcd(i, j)，保证 n, m 不超过 1e5

题解：

有没有感觉像莫比乌斯反演？可惜我已经不会了

还是数学题基本操作：

改变枚举对象： 枚举公约数

\sum_{yue = 1}^{max(n, m)} \sum_{i = 1}^{n} \sum_{j = 1}^{m} [gcd(i, j) = yue]

再按照莫反的套路：

\sum_{yue = 1}^{max(n, m)} {floor(\frac{n}{yue}) * floor(\frac{m}{yue}) - illegal~part}

设 f[i] 表示公约数为i或i的倍数的个数。

设 g[i] 表示公约数恰好为i的个数。

ans = \sum g[i]

其中 g[i] 大概就是上面的那个大长式子。有没有感受到浓浓的莫反气息？

我们可以暴力地去删去 illegal ~ part，这部分其实就是所有 公约数恰为 i 的倍数（不含1倍）的数对个数，即：

g[i] = f[i] - \sum_{j = 2}^{j * i <= max(n, m)}g[i * j]

发现可以dp处理！！

复杂度为 \sum_{i = 1}^{n}\frac{n}{i} = n~lnn

P4778 Counting swaps

题意：

给一个长度为 n 的排列 p_i，求使之成为 1 ~ 2 ... n 的最小操作次数和此前提下的可行方案数.(n <= 1e5)

题解：

介绍一下排列交换的套路：

先把 i 和 p_i 连边，然后我们会发现出现了许多环。每次操作最多可以让环的个数加一。最终排列的环的个数为 n （全部为自环）。因此，最小操作次数为： n - 一开始的环的个数。

然后考虑求方案数。我们设 f[i] 表示将长度为 i 的环全部断成自环的方案数，那么转移方程为：

f[i] = \sum_{x + y = i}{g(x, y) * f[x] * f[y] * \frac{i!}{x! * y!}}

其中：

g(x, y) = x(when~x = y) g(x, y) = x + y(when~x \not= y)

解释一下f[i]:考虑将i断成两部分，长度分别为 x, y，递归下去，应该乘 f[x] * f[y]。

然后考虑有多少种断的方案，这一部分我们用 g(x, y) 来表示断成 x, y 两段的方案：

通过手玩可知枚举两个断点之一，那么另一个端点应该有两个（x = y的情况除外），然后发现每个点都计了两次，因此再除以2.

最后发现还有些不对劲，因为并不是先去断 x，再去断 y，他们是可以交错进行的！因此还要规定他们的排列次序。这是一个可重集合的全排列的模型，可以看作求出全排列后再对每一个相同元素除去有序性。（详见lyd的《算法竞赛进阶指南》）

最后总方案数与 f 的求法类似，为：

Ans = \Pi_{i = 1}^{ctot}{f[i]} * \frac{n-ctot}{\Pi_{i=1}^{ctot}siz[i]}

就可以 O(n^2) 解决了。（瓶颈在 f[i] 的求法）

进一步优化:通过打表可知： f[i] = n^{n-2}，然后就 O(nlogn)了。

my record

CF24D Broken robot

题意

给一个 n * m 方格，起始位置为 (x, y)，每次可以选择停留，向下走，向左走，向右走（不允许越界），每个位置的每种合法选择的概率相等。求走到最后一行的期望次数。

n, m <= 1000

题解

题目其实就是从 (x, y) 走到 (n, ...) 的期望步数。这有点像“随机游走”模型。我们设置 (n, ...) 为 T，f[i][j] 表示从 (i, j) 走到 T 的期望步数。然后类似“绿豆蛙的归宿”，逆着跑dp，其中 f[i][j] = \frac{f[i][j] + f[i + 1][j] + f[i][j - 1] + f[i][j + 1]}{4} + 1。 这个可以 O((nm)^3) 高斯消元。

然后我们发现 f[i][j] 只与它左右以及下一行有关，并且最后一行的 f 已知（为0）。因此我们似乎可以一行一行地推。复杂度：O(nm^3)

然后发现系数矩阵比较特殊，大部分为0，只有对角线部分非零。具体长这样。因此我们模拟高斯消元法（注意，不是高斯-约旦），从上到下消一遍，从下到上再消一遍，然后就出答案了。一遍高消复杂度 O(m)，故总复杂度为 O(nm)。

类似的题：P4457 [BJOI2018]治疗之雨（这个的系数矩阵是下三角矩阵，只需把高消修改为 O(n^2) 来模拟即可）

CF1332E Height All the Same

问题的关键点：求出范围为 [L, R] 的 m（m为偶数） 个数（有编号）中奇数出现了偶数次的方案一共有多少种。

列一下式子：设 tot = R - L + 1; odd = R - L + 1 中的奇数个数。那么需要求的就是：

C_{m}^{0}odd^0 * (tot - odd)^m + C_{m}^{2}odd^2 * (tot - odd)^{m - 2} + C_{m}^{4}odd^4 * (tot - odd)^{m - 4} + ... + C_{m}^{m}odd^m * (tot - odd)^{0}

然后发现和二项式展开的形式差不多，二项式展开：

(x + y)^n = C_{m}^{0}x^0 * y^n + C_{m}^{1}x^1 * y^{n - 1} + C_{m}^{2}x^2 * y^{n - 2} + ... + C_{m}^{m}x^m * y^{0}

但是唯一不同的是，第一个式子缺少次数为奇数的那些项。又因为：

(x - y)^n = C_{m}^{0}x^0 * y^n - C_{m}^{1}x^1 * y^{n - 1} + C_{m}^{2}x^2 * y^{n - 2} + ... + C_{m}^{m}x^m * y^{0}

二者正好可以抵消掉次数为奇数的那些项。因此二者相加再除以2即可。即：

answer = ((odd + tot - odd)^m + (odd - tot + odd)^m) / 2

CF140E New Year Garland

题意:

n层小球要涂色，有m种颜色可以选择，第i层有l[i]个小球。要求每一层的小球相邻的颜色不可相同，相邻层的小球的颜色集合不可相同。求合法方案数模p的值。（p不一定为质数）

n,m<=1e6;p<=1e9;l[i]<=5000;\sum l[i] <= 1e7

题解：

dp。设f[i][j]表示i个小球选择j种颜色（无编号）的方案数。g[x][y]表示选择到了第x行，且第x行恰好选择了y种颜色的方案数。

转移：

（考虑最后一个小球的颜色是否为新颜色）

f[i][j] = f[i - 1][j] * (j - 1) + f[i - 1][j - 1]

（考虑所有方案减去不合法方案）

g[x][y] = C_m^y * f[l[i]][y] * y! * sum - g[x-1][y] * f[l[i]][y] * y!

其中:sum 表示前 x-1 行的所有方案数。

然后各种优化dp即可。

my record