力扣刷题笔记 #09 数学

本文包含「数学」类型题中的：乘法原理、乘法逆元、素数筛、组合数公式、不等式等。持续更新中。

题目描述：

方法1：

方法2：

方法3：

坑点：

乘法原理

通常场景为「所有子数组的 XX 之和」、「所有子串的 XX 之和」，并且会有一个元素被多个子数组/子串统计多次的情况。枚举每个子数组必定超时，正确的做法是枚举每个元素作为 XX 的最远边界，再利用乘法原理计算该元素能作为多少个「子数组的 XX」，即每个元素的贡献度。 \[ \sum_{i=0}^{n-1} \operatorname{arr}[i] \times \operatorname{left}[i] \times \operatorname{right}[i] \] 计算最远边界时通常采用单调栈预处理，并记录下标距离。如果原数组中有重复元素，为了防止包含重复元素的子数组被重复考虑，需要修改边界定义，采用不对称区间，即一侧可以跨越 \(x\)，另一侧不可以。

828. 统计子串中的唯一字符 (H)

题目描述：定义函数 countUniqueChars(t) 来统计字符串 t 中的唯一字符个数，给定字符串 s，要求返回所有连续子串的函数值之和。

方法1：乘法原理，每个元素产生贡献仅当其只出现一次时，所以两侧边界就是该元素本身，预处理得到每个元素两侧第一个相同元素，再遍历一次算出总和。时空复杂度均为 \(O(n)\)。

方法2：空间优化，只需记录每个字母近两次出现的位置，当遇到第三个次时即可算中间的字母，空间复杂度 \(O(1)\)。

907. 子数组的最小值之和 (M)

题目描述：给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个连续子数组。

方法1：单调栈 + 乘法原理，用两个单调递增栈预处理得到 \(arr[i]\) 左边第一个 \(<arr[i]\) 的下标，右边第一个 \(\leqslant arr[i]\) 的下标，得到不对称区间，两边相乘计算贡献。时空复杂度均为 \(O(n)\)。

方法2：一个单调栈做法，在第一个栈预处理左边界时，栈顶元素 \(\geqslant arr[i]\) 需要 pop，此时 \(i\) 恰好是栈顶元素的右边界，可以一起标记。时空复杂度均为 \(O(n)\)。

方法3：进一步地，由于栈顶下面的元素正好也是栈顶元素的左边界，所以甚至连 \(left\) 和 \(right\) 数组都不需要，直接在栈的时候计算贡献，为简化代码逻辑，可以在遍历前往 \(arr\) 末尾和栈顶分别加一个 \(−1\)，当作哨兵。

1856. 子数组最小乘积的最大值 (M)

题目描述：一个数组的最小乘积定义为这个数组中最小值乘以数组的和，给定一个正整数数组，求子数组中最小乘积的最大值。

方法：单调栈 + 前缀和 + 乘法原理，单调栈处理得到不对称区间，预处理前缀和，每个数算出最小乘积，复杂度 \(O(n)\)。

坑点：题目明确「保证最小乘积的最大值在不取余的情况下可以用 64 位有符号整数保存」，取 max 前千万不能取模，必须在返回值处取模，否则答案会出错。

THUOJ 最强战力 (H)

题目描述：有一个 HERO 数组，存放每一名英雄的战力值，从中取出连续的一组英雄组成一个小队，小队的战力值定义为「小队中最弱战力 \(\times\) 小队总战力」，计算所有可能小队的小队战力值之和。

方法：单调栈 + 乘法原理，一个单调栈处理得到 \(hero[i]\) 左边第一个 \(<hero[i]\) 的下标，右边第一个 \(\leqslant hero[i]\) 的下标，得到不对称区间。记一个元素会被乘 \(times[i]\) 次，遍历每一个元素对周围元素的 \(times\) 影响，时间复杂度 \(O(n^2)\)。

对于每个元素 \(hero[i]\)，其左边的元素 \(hero[x]\) 会被 \(hero[i]\) 影响 \(hero[i]\times (l[i]-i)\times (x-r[i])\) 次，右边的元素同理。根据两边是否有元素，需要分四种情况讨论。

最后算出每个元素被两侧元素的累计影响（包括自身对自身的影响）的 \(times\)，则其贡献就是 \(hero[i]\times times[i]\)。

2104. 子数组范围和 (M)

题目描述：一个整数数组，定义子数组的范围是子数组中最大元素和最小元素的差值，求所有子数组的范围和。

方法1：暴力，两层循环，外循环枚举左端点，内循环枚举右端点并 DP 处理前缀最值，时间复杂度 \(O(n^2)\)。

方法2：乘法原理 + 交换律，要求「最大元素减去最小元素」之和，等价于求「最大元素之和」减去「最小元素之和」，用两个单调栈分别计算两个子问题，最后求差值即可。时间复杂度 \(O(n)\)。

891. 子序列宽度之和 (H)

题目描述：一个整数数组，定义子序列的宽度是子序列中最大元素和最小元素的差值，求所有子序列的宽度和。

方法1：排序 + 数学，由于子序列的顺序对结果不会产生影响，所以可以对数组先排序。此时每个元素都是其左边的元素的最大值，右边元素的最小值，可以算出每个数作为最大值的次数和最小值的次数（贡献）。时间复杂度 \(O(n \log n)\)。

以排序后的数字 \(nums[i]\) 为例，其左边有 \([0,i-1]\) 共 \(i\) 个元素，每个元素按照是否出现，总共有 \(2^i\) 种子序列；右边有 \([i+1, n-1]\) 共 \(n-i-1\) 个元素，总共有 \(2^{n-i-1}\) 种子序列。需要 \(O(n)\) 预处理 \(2\) 的所有幂次才可直接求和。

方法2：递推处理幂次，方法 1 需要额外存储 \(2\) 的每次，但其实可以直接递推计算 \(2^i\) 和 \(2^{n-i-1}\)，后者需要用到 \(2\) 关于 \(10^9+7\) 的逆元，空间复杂度优化到 \(O(1)\)。

方法3：另一种思路，计算 \(2^i\) 对答案的贡献度，即 \((nums[i]-nums[n-1-i])\times 2^i\)，空间复杂度也是 \(O(1)\)。

乘法逆元

定义：对于一个实数 \(a\)，如果存在一个 \(x\) 使得 \(ax=1 \textrm{ mod } p\)，则称 \(x\) 是 \(a\) 关于 \(p\) 的逆元。此处要求 \(p\) 与 \(a\) 互质，即满足 \(\mathrm{gcd}(a,p)=1\)。

常见问法：返回分数 \(\frac{a}{b}\) 关于 \(p\) 的模，由于除法不满足模不变性，此时需要用 \(a\) 乘以 \(b\) 关于 \(p\) 的逆元。

最简单的方法，由费马小定理得到 \(a\) 关于 \(p\) 的逆元为 \(a^{p-2}\)，要求 \(p\) 是质数，结合快速幂 \(O(\log n)\) 模板：

// 非递归快速幂，带 mod 运算
ll qpowmod(ll a, ll n, ll mod) {
	ll ans = 1;
	while(n){
		if(n & 1) ans = (ans * a) % mod;
		a = (a * a) % mod;
		n >>= 1;
	}
	return ans % mod;
}
ll x = qpowmod(a, p - 2, p);

扩展欧几里得：\(ax+py=\textrm{gcd}(a,p)\) 一定有解，此时不要求 \(p\) 为质数，但 \(\mathrm{gcd}(a,p)=1\) 必须满足。复杂度 \(O(\log n)\)：

ll x, y; // 用于递归的全局变量
void Exgcd(ll a, ll b, ll &x, ll &y) {
	if (!b) x = 1, y = 0;
	else Exgcd(b, a % b, y, x), y -= a / b * x;
}
Exgcd(a, p, x, y); // 返回的逆元存放在 x 中

最后是线性递推 \(O(n)\) 求连续数的逆元，注意 \(p\) 必须为质数，否则 \(p\;\%\; i\) 可能为零：

ll inv[100001], p;
ll Inv(ll i) {
	if(i == 1) return 1;
	return (p - p / i) * Inv(p % i) % p;
}

素数筛

埃氏筛，\(O(n \log(\log n))\)，空间占用小，返回布尔数组，适用于快速判断素数，最高支持 \(1e8\)，模板如下：

const int maxn = 1e8 + 10;
bool isprime[maxn]; //布尔数组，1表示质数
void Esieve(int n){
    // 所有偶数先赋值 0，奇数还是 1
	for(int i = 0, d = 0; i <= n; i++, d ^= 1) isprime[i] = d; 
	isprime[1] = 0, isprime[2] = 1;	// 特判
    // 从 3 开始排除，因为偶数已经全被排除，2没用
	for (int i = 3; i <= sqrt(n) + 1; i++){
		if (isprime[i]){
            // i 必为奇数，i*i 也为奇数，偶数跳过
			for (int j = i * i; j <= n; j += 2 * i) isprime[j] = 0;
		}
	}
}

欧式筛，\(O(n)\)，空间占用大，适用于从零开始顺序打表，最高支持 \(1e8\)，模板如下：

const int maxn = 1e6 + 10;
int v[maxn];		// 合数标记，存放最小质因数
int prime[maxn];	// 顺序存储质数，注意末尾有 0
int cnt = 0;		// 素数个数
void Osieve(int n) {
    memset(v, 0, sizeof(v)); // 假设全为素数
    for(int i = 2; i <= n; i++) {
        if(!v[i]) {
            prime[++cnt] = i;
            v[i] = i;
        }
        for(int j = 1; j <= cnt; j++) {
            if(prime[j] > v[i] || prime[j] * i > n) break;
            v[prime[j] * i] = prime[j];
        }
    }
}

排列数与组合数

组合数的定义：\(C_i^j=\frac{i!}{j!(i-j)!}\)，排列数定义：\(A_i^j=\frac{i!}{(i-j)!}\)

组合数和式：

• \(C_n^0+C_n^1+C_n^2+\cdots+C_n^n=2^n\)
• \(1 C_n^1+2 C_n^2+3 C_n^3+\cdots+n C_n^n=n 2^{n-1}\)
• \(1^2 C_n^1+2^2 C_n^2+3^2 C_n^3+\cdots+n^2 C_n^n=n(n+1) 2^{n-2}\)
• \(\left(C_n^0\right)^2+\left(C_n^1\right)^2+\left(C_n^2\right)^2+\cdots+\left(C_n^n\right)^2=C_{2 n}^n\)

排列数和式：

• \(A_n^0+A_n^1+A_n^2+\cdots+A_n^n=\mathrm{INT}(n!\cdot e)\)

快速求组合数：

• 定义法计算较小的单值，只需要 \(\mathcal{O}(\min(j,i-j))\) 的时间和 \(\mathcal{O}(1)\) 的空间。不能用于多值、可能溢出的较大值。

• 递推：可以用 \(C_i^j=C_{i-1}^j+C_{i-1}^{j-1}\) 的递推式 \(\mathcal{O}\left(k^2\right)\) 求组合数。

• 递推：可以通过 \(C_k^i=\frac{k-i+1}{i} C_k^{i-1}\) 的递推式 \(\mathcal{O}(k)\) 求组合数，分母的 \(i\) 需要用乘法逆元计算。

• 线性求逆元：for(int i = 2; i <= K; i++) inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;

62. 不同路径 (M)

题目描述：一个机器人位于一个 m x n 网格的左上角，试图达到网格的右下角，求路径数目。

方法1：DP，用 \(dp[i][j]\) 表示从左上角走到 \((i,j)\) 的路径数，首行和首列初始化为 1，时空复杂度均为 \(O(n^2)\)。 \[ dp[i][j]=dp[i-1][j] + dp[i][j-1] \] 方法2：DP + 滚动数组，下一个状态只由最近两行的状态转移，因此可以用两行数组，空间复杂度为 \(O(n)\)。

方法3：组合数公式，从左上角到右下角的过程中，总共需要走 \(m+n-2\) 步，其中必有 \(m-1\) 步向下，其余向右。因此答案就是 \(C^{m-1}_{m+n-2}\)。数字较小可以直接用定义计算，时间复杂度 \(O(\min(m,n))\)，空间复杂度 \(O(1)\)。

2400. 恰好移动 k 步到达某一位置的方法数目 (M)

题目描述：给定数轴上的两个整数 startPos 和 endPos 代表起点和终点，每次可以向左或向右移动一步，求 k 步后从起点恰好移动到终点的方案数。

方法1：记忆化搜索，即起点到终点的距离为 \(n\)，则有 dfs(k,n)=dfs(k-1,n-1)+dfs(k-1,n+1);，利用 visited 数组剪枝，复杂度 \(O(k^2)\)。

方法2：动态规划，状态转移方程同上，但是从 \(k=0\) 开始递推，复杂度 \(O(k^2)\)。

方法3：组合数公式，假设往正方向走 \(a\) 步，负方向走 \(k-a\) 到达，从 \(k\) 步中选 \(a\) 步的结果为 \(C_{k}^{a}\)。由 \(a-(k-a)=n\) 得 \(a=\frac{k+n}{2}\)。因此要先判断 \((n+k)\) 为偶数，然后求组合数。最优复杂度 \(O(k)\)。

坑点：使用 visited 数组、DP 数组时，要注意 n-k 可能的下标越界问题，需要整体向右平移。

754. 到达终点数字 (M)

题目描述：给定数轴上的 target 表示终点，起点在 \(0\)。每次可以向左或向右移动，第 \(i\) 次移动走 \(i\) 步，计算到达终点所需的最小移动次数。

方法：组合数思想，设 \(k\) 为最小的满足 \(s=\sum_{i=1}^k{\geqslant target}\) 的正整数，如果 \(s=target\) 则答案就是 \(k\)，否则需要在部分整数前添加负号来将和凑到目标。如果这个差值 $$ 是偶数，则必然可以从 \(1\) 到 \(k\) 中凑出若干整数和为 \(\varDelta / 2\)；如果是奇数，则无法整除 \(2\)，考虑 \(k+1\) 和 \(k+2\)，其中必有一个是奇数，可以改变 $$ 的奇偶性，此时满足题意。

绝对值中位数不等式

$( ) $ 问题，当 \(x\) 取中位数时，总和达到最小值。如果中位数有两个，则这两个数构成的区间内任意取值都可以。

296. 最佳的碰头地点 (M)

题目描述：在 \(n\times n\) 网格中有 \(m\) 个人，在网格中选择一个点作为碰头地点，最小化他们的总行走距离。距离采用曼哈顿距离，即 distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|。

方法1：暴力，横纵坐标可以分开处理，遍历所有可选的网格，计算与每个人的距离，时间复杂度 \(O(nm)\)。

方法2：排序，从左往右遍历时，每右移一格，总距离「加上左边的人数、减去右边的人数」，维护一个变量记录左边的人数，只需遍历一轮，时间复杂度 \(O(m \log m +n)\)，遍历复杂度可以优化到 \(O(m)\)。

方法3：绝对值中位数贪心，由方法 2 可知，当左右两边人数相等时，总距离达到最小值。如果 \(n\) 为奇数，则返回中位数；否则可以在中位数两侧的数构成的区间内任意取值。nth_element() 求中位数复杂度为 \(O(m)\)。

2448. 使数组相等的最小开销 (H)

题目描述：给定数组 nums 和 cost，分别包含 \(n\) 个正整数。要将 nums 中的所有元素修改为相等，每次可以对一个元素增一或减一，每次操作的代价为 cost 中的对应元素，求最小总开销。

方法1：排序，将两个数组捆绑排序，先计算使所有元素都等于 \(nums[0]\) 的开销，以及 \(sumCost\)。目标数每增一，则总开销「加上 \(cost[0]\)，减去 \(sumCost-cost[0]\)」，时间复杂度 \(O(n \log n)\)。

方法2：绝对值中位数贪心，$( ) $ 问题，按 \(a_i\) 拆分，考虑全体的中位数即可。这里先排序，然后遍历时累加 \(cost\)，直到突破 \(sumCost/2\) 即可得到中位数。时间复杂度 \(O(n\log n)\)。

对于 $( ) $ 问题，当 \(a_i=1\) 时，最优解就是 \(x\) 取中位数的时候。如果 \(a_i\) 为任意正整数，则可以将其拆分为 \(a_i\) 个系数为 \(1\) 的绝对值表达式求和，接下来依然考虑中位数即可。

拒绝采样

拒绝采样常用于随机事件的生成：通过多次采样已知的随机事件，并拒绝（重采样）部分情况，则可达到目标概率。

采样已知事件次数的期望可以用被拒绝的概率等比数列求和，假设每轮需要采样 \(n\) 次组合，拒绝概率为 \(p\)： \[ \mathbb{E} =n+n\cdot p+n\cdot p^2+\cdots +n\cdot p^{\infty} \\ =n\sum_{i=0}^{\infty}{p^i}=\frac{n}{1-p} \]

470. 用 Rand7 实现 Rand10 (M)

题目描述：给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，将其改写为 rand10。

方法1：先组合再拒绝，将两次 rand7 组合成 \((x,y)\)，共 \(49\) 种结果，映射 \(idx=x+(y-1)\times 7\)，则 \(idx\) 范围 \([1,49]\)，拒绝 \(idx>40\) 的情况，返回 \(1+idx\;\%\;10\) 即可。

该方法调用 rand7 次数的期望是 \(\frac{2}{1-\frac{9}{49}}=2.45\)，为了减少次数，需要减小随机被拒绝的概率：合理地使用被拒绝的采样。若 \(idx\) 在 \([41,49]\) 之间，相当于一个 \([1,9]\) 的随机数，如果在调用一次 rand7，就可以得到 \([1,63]\)，保留 \([1,60]\) 并拒绝 \([61,63]\)，得到一个 \([1,3]\) 的随机数，以此类推。

方法2：先拒绝再组合，第一次 rand7 构造 \(\frac{1}{2}\) 概率（拒绝 \(7\) 后取奇偶），第二次 rand7 构造 \(\frac{1}{5}\) 概率（拒绝 \([6,7]\) 得到 \(idx\)）。如果第一次是奇数就返回 \(idx\)，偶数就返回 \(idx+5\)。

方法3：

坑点：千万不能使用两个 rand7 相乘、相加的做法，否则映射的结果不均匀！