fork()==0世界线变动

2543. 判断一个点是否可以到达

给你一个无穷大的网格图。一开始你在 (1, 1) ，你需要通过有限步移动到达点 (targetX, targetY) 。

每一步 ，你可以从点 (x, y) 移动到以下点之一：

• (x, y - x)

• (x - y, y)

• (2 * x, y)

• (x, 2 * y)

给你两个整数 targetX 和 targetY ，分别表示你最后需要到达点的 X 和 Y 坐标。如果你可以从 (1, 1) 出发到达这个点，请你返回true ，否则返回 false 。

示例 1：

```txt

输入：targetX = 6, targetY = 9

输出：false

解释：没法从 (1,1) 出发到达 (6,9) ，所以返回 false 。

```

示例 2：

```txt

输入：targetX = 4, targetY = 7

输出：true

解释：你可以按照以下路径到达：(1,1) -> (1,2) -> (1,4) -> (1,8) -> (1,7) -> (2,7) -> (4,7) 。

```

提示：

• 1 <= targetX, targetY <= 10^9

1819. 序列中不同最大公约数的数目

给你一个由正整数组成的数组 nums 。

数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。

• 例如，序列 [4,6,16] 的最大公约数是 2 。

数组的一个 子序列 本质是一个序列，可以通过删除数组中的某些元素（或者不删除）得到。

• 例如，[2,5,10] 是 [1,2,1,**2**,4,1,**5**,**10**] 的一个子序列。

计算并返回 nums 的所有 非空 子序列中 不同 最大公约数的 数目 。

示例 1：

```txt

输入：nums = [6,10,3]

输出：5

解释：上图显示了所有的非空子序列与各自的最大公约数。

不同的最大公约数为 6 、10 、3 、2 和 1 。

```

示例 2：

```txt

输入：nums = [5,15,40,5,6]

输出：7

```

提示：

• 1 <= nums.length <= 10^5

• 1 <= nums[i] <= 2 * 10^5

2183. 统计可以被 K 整除的下标对数目

给你一个下标从 0 开始、长度为 n 的整数数组 nums 和一个整数 k ，返回满足下述条件的下标对 (i, j) 的数目：

• 0 <= i < j <= n - 1 且

• nums[i] * nums[j] 能被 k 整除。

示例 1：

```txt

输入：nums = [1,2,3,4,5], k = 2

输出：7

解释：

共有 7 对下标的对应积可以被 2 整除：

(0, 1)、(0, 3)、(1, 2)、(1, 3)、(1, 4)、(2, 3) 和 (3, 4)

它们的积分别是 2、4、6、8、10、12 和 20 。

其他下标对，例如 (0, 2) 和 (2, 4) 的乘积分别是 3 和 15 ，都无法被 2 整除。

```

示例 2：

```txt

输入：nums = [1,2,3,4], k = 5

输出：0

解释：不存在对应积可以被 5 整除的下标对。

```

提示：

• 1 <= nums.length <= 10^5

• 1 <= nums[i], k <= 10^5

1157. 子数组中占绝大多数的元素

设计一个数据结构，有效地找到给定子数组的 多数元素 。

子数组的 多数元素 是在子数组中出现 threshold 次数或次数以上的元素。

实现 MajorityChecker 类:

• MajorityChecker(int[] arr) 会用给定的数组 arr 对 MajorityChecker 初始化。

• int query(int left, int right, int threshold) 返回子数组中的元素  arr[left...right] 至少出现 threshold 次数，如果不存在这样的元素则返回 -1。

示例 1：

```txt

输入:

["MajorityChecker", "query", "query", "query"]

[[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]]

输出：

[null, 1, -1, 2]

解释：

MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);

majorityChecker.query(0,5,4); // 返回 1

majorityChecker.query(0,3,3); // 返回 -1

majorityChecker.query(2,3,2); // 返回 2

```

提示：

• 1 <= arr.length <= 2 * 10^4

• 1 <= arr[i] <= 2 * 10^4

• 0 <= left <= right < arr.length

• threshold <= right - left + 1

• 2 * threshold > right - left + 1

• 调用 query 的次数最多为 10^4

1621. 大小为 K 的不重叠线段的数目

给你一维空间的 n 个点，其中第 i 个点（编号从 0 到 n-1）位于 x = i 处，请你找到 恰好 k 个不重叠 线段且每个线段至少覆盖两个点的方案数。线段的两个端点必须都是 整数坐标 。这 k 个线段不需要全部覆盖全部 n 个点，且它们的端点 可以 重合。

请你返回 k 个不重叠线段的方案数。由于答案可能很大，请将结果对 10^9 + 7 取余 后返回。

示例 1：

```txt

输入：n = 4, k = 2

输出：5

解释：

如图所示，两个线段分别用红色和蓝色标出。

上图展示了 5 种不同的方案 {(0,2),(2,3)}，{(0,1),(1,3)}，{(0,1),(2,3)}，{(1,2),(2,3)}，{(0,1),(1,2)} 。

```

示例 2：

```txt

输入：n = 3, k = 1

输出：3

解释：总共有 3 种不同的方案 {(0,1)}, {(0,2)}, {(1,2)} 。

```

示例 3：

```txt

输入：n = 30, k = 7

输出：796297179

解释：画 7 条线段的总方案数为 3796297200 种。将这个数对 109 + 7 取余得到 796297179 。

```

示例 4：

```txt

输入：n = 5, k = 3

输出：7

```

示例 5：

```txt

输入：n = 3, k = 2

输出：1

```

提示：

• 2 <= n <= 1000

• 1 <= k <= n-1

100127. 给小朋友们分糖果 II

给你两个正整数 n 和 limit 。

请你将 n 颗糖果分给 3 位小朋友，确保没有任何小朋友得到超过 limit 颗糖果，请你返回满足此条件下的 总方案数 。

示例 1：

```txt

输入：n = 5, limit = 2

输出：3

解释：总共有 3 种方法分配 5 颗糖果，且每位小朋友的糖果数不超过 2 ：(1, 2, 2) ，(2, 1, 2) 和 (2, 2, 1) 。

```

示例 2：

```txt

输入：n = 3, limit = 3

输出：10

解释：总共有 10 种方法分配 3 颗糖果，且每位小朋友的糖果数不超过 3 ：(0, 0, 3) ，(0, 1, 2) ，(0, 2, 1) ，(0, 3, 0) ，(1, 0, 2) ，(1, 1, 1) ，(1, 2, 0) ，(2, 0, 1) ，(2, 1, 0) 和 (3, 0, 0) 。

```

提示：

• 1 <= n <= 10^6

• 1 <= limit <= 10^6

2514. 统计同位异构字符串数目

给你一个字符串 s ，它包含一个或者多个单词。单词之间用单个空格 ' ' 隔开。

如果字符串 t 中第 i 个单词是 s 中第 i 个单词的一个 排列 ，那么我们称字符串 t 是字符串 s 的同位异构字符串。

• 比方说，"acb dfe" 是 "abc def" 的同位异构字符串，但是 "def cab" 和 "adc bef" 不是。

请你返回 s 的同位异构字符串的数目，由于答案可能很大，请你将它对 10^9 + 7 取余 后返回。

示例 1：

```txt

输入：s = "too hot"

输出：18

解释：输入字符串的一些同位异构字符串为 "too hot" ，"oot hot" ，"oto toh" ，"too toh" 以及 "too oht" 。

```

示例 2：

```txt

输入：s = "aa"

输出：1

解释：输入字符串只有一个同位异构字符串。

```

提示：

• 1 <= s.length <= 10^5

• s 只包含小写英文字母和空格 ' ' 。

• 相邻单词之间由单个空格隔开。