fork()==0世界线变动

2851. 字符串转换

You are given two strings s and t of equal length n. You can perform the following operation on the string s:

• Remove a suffix of s of length l where 0 < l < n and append it at the start of s.

  For example, let s = 'abcd' then in one operation you can remove the suffix 'cd' and append it in front of s making s = 'cdab'.

You are also given an integer k. Return the number of ways in which s can be transformed into t in exactly k operations.

Since the answer can be large, return it modulo 10^9 + 7.

Example 1:

```txt

Input: s = "abcd", t = "cdab", k = 2

Output: 2

Explanation:

First way:

In first operation, choose suffix from index = 3, so resulting s = "dabc".

In second operation, choose suffix from index = 3, so resulting s = "cdab".

Second way:

In first operation, choose suffix from index = 1, so resulting s = "bcda".

In second operation, choose suffix from index = 1, so resulting s = "cdab".

```

Example 2:

```txt

Input: s = "ababab", t = "ababab", k = 1

Output: 2

Explanation:

First way:

Choose suffix from index = 2, so resulting s = "ababab".

Second way:

Choose suffix from index = 4, so resulting s = "ababab".

```

Constraints:

• 2 <= s.length <= 5 * 10^5

• 1 <= k <= 10^15

• s.length == t.length

• s and t consist of only lowercase English alphabets.

6456. 矩阵中严格递增的单元格数

给你一个下标从 1 开始、大小为 m x n 的整数矩阵 mat，你可以选择任一单元格作为 起始单元格 。

从起始单元格出发，你可以移动到 同一行或同一列 中的任何其他单元格，但前提是目标单元格的值 严格大于 当前单元格的值。

你可以多次重复这一过程，从一个单元格移动到另一个单元格，直到无法再进行任何移动。

请你找出从某个单元开始访问矩阵所能访问的 单元格的最大数量 。

返回一个表示可访问单元格最大数量的整数。

示例 1：

```txt

输入：mat = [[3,1],[3,4]]

输出：2

解释：上图展示了从第 1 行、第 2 列的单元格开始，可以访问 2 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 2 个单元格，因此答案是 2 。

```

示例 2：

```txt

输入：mat = [[1,1],[1,1]]

输出：1

解释：由于目标单元格必须严格大于当前单元格，在本示例中只能访问 1 个单元格。

```

示例 3：

```txt

输入：mat = [[3,1,6],[-9,5,7]]

输出：4

解释：上图展示了从第 2 行、第 1 列的单元格开始，可以访问 4 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 4 个单元格，因此答案是 4 。

```

提示：

• m == mat.length 

• n == mat[i].length 

• 1 <= m, n <= 10^5

• 1 <= m * n <= 10^5

• -10^5 <= mat[i][j] <= 10^5

1201. 丑数 III

给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。

丑数是可以被 a 或 b 或 c 整除的 正整数 。

示例 1：

```txt

输入：n = 3, a = 2, b = 3, c = 5

输出：4

解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。

```

示例 2：

```txt

输入：n = 4, a = 2, b = 3, c = 4

输出：6

解释：丑数序列为 2, 3, 4, 6, 8, 9, 10, 12... 其中第 4 个是 6。

```

示例 3：

```txt

输入：n = 5, a = 2, b = 11, c = 13

输出：10

解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。

```

示例 4：

```txt

输入：n = 1000000000, a = 2, b = 217983653, c = 336916467

输出：1999999984

```

提示：

• 1 <= n, a, b, c <= 10^9

• 1 <= a * b * c <= 10^18

• 本题结果在 [1, 2 * 10^9] 的范围内

2009. 使数组连续的最少操作数

给你一个整数数组 nums 。每一次操作中，你可以将 nums 中 任意 一个元素替换成 任意 整数。

如果 nums 满足以下条件，那么它是 连续的 ：

• nums 中所有元素都是 互不相同 的。

• nums 中 最大 元素与 最小 元素的差等于 nums.length - 1 。

比方说，nums = [4, 2, 5, 3] 是 连续的 ，但是 nums = [1, 2, 3, 5, 6] 不是连续的 。

请你返回使 nums 连续 的 最少 操作次数。

示例 1：

```txt

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

输出：0

解释：nums 已经是连续的了。

```

示例 2：

```txt

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

输出：1

解释：一个可能的解是将最后一个元素变为 4 。

结果数组为 [1,2,3,5,4] ，是连续数组。

```

示例 3：

```txt

输入：nums = [1,10,100,1000]

输出：3

解释：一个可能的解是：

• 将第二个元素变为 2 。

• 将第三个元素变为 3 。

• 将第四个元素变为 4 。

结果数组为 [1,2,3,4] ，是连续数组。

```

提示：

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

• 1 <= nums[i] <= 10^9

1482. 制作 m 束花所需的最少天数

给你一个整数数组 bloomDay，以及两个整数 m 和 k 。

现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。

花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。

请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。

示例 1：

```txt

输入：bloomDay = [1,10,3,10,2], m = 3, k = 1

输出：3

解释：让我们一起观察这三天的花开过程，x 表示花开，而 _ 表示花还未开。

现在需要制作 3 束花，每束只需要 1 朵。

1 天后：[x, , , , ] // 只能制作 1 束花

2 天后：[x, , , _, x] // 只能制作 2 束花

3 天后：[x, , x, , x] // 可以制作 3 束花，答案为 3

```

示例 2：

```txt

输入：bloomDay = [1,10,3,10,2], m = 3, k = 2

输出：-1

解释：要制作 3 束花，每束需要 2 朵花，也就是一共需要 6 朵花。而花园中只有 5 朵花，无法满足制作要求，返回 -1 。

```

示例 3：

```txt

输入：bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3

输出：12

解释：要制作 2 束花，每束需要 3 朵。

花园在 7 天后和 12 天后的情况如下：

7 天后：[x, x, x, x, _, x, x]

可以用前 3 朵盛开的花制作第一束花。但不能使用后 3 朵盛开的花，因为它们不相邻。

12 天后：[x, x, x, x, x, x, x]

显然，我们可以用不同的方式制作两束花。

```

示例 4：

```txt

输入：bloomDay = [1000000000,1000000000], m = 1, k = 1

输出：1000000000

解释：需要等 1000000000 天才能采到花来制作花束

```

示例 5：

```txt

输入：bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2

输出：9

```

提示：

• bloomDay.length == n

• 1 <= n <= 10^5

• 1 <= bloomDay[i] <= 10^9

• 1 <= m <= 10^6

• 1 <= k <= n

911. 在线选举

给你两个整数数组 persons 和 times 。在选举中，第 i 张票是在时刻为 times[i] 时投给候选人 persons[i] 的。

对于发生在时刻 t 的每个查询，需要找出在 t 时刻在选举中领先的候选人的编号。

在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。

实现 TopVotedCandidate 类：

• TopVotedCandidate(int[] persons, int[] times) 使用 persons 和 times 数组初始化对象。

• int q(int t) 根据前面描述的规则，返回在时刻 t 在选举中领先的候选人的编号。

示例：

```txt

输入：

["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]

[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]

输出：

[null, 0, 1, 1, 0, 0, 1]

解释：

TopVotedCandidate topVotedCandidate = new TopVotedCandidate([0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]);

topVotedCandidate.q(3); // 返回 0 ，在时刻 3 ，票数分布为 [0] ，编号为 0 的候选人领先。

topVotedCandidate.q(12); // 返回 1 ，在时刻 12 ，票数分布为 [0,1,1] ，编号为 1 的候选人领先。

topVotedCandidate.q(25); // 返回 1 ，在时刻 25 ，票数分布为 [0,1,1,0,0,1] ，编号为 1 的候选人领先。（在平局的情况下，1 是最近获得投票的候选人）。

topVotedCandidate.q(15); // 返回 0

topVotedCandidate.q(24); // 返回 0

topVotedCandidate.q(8); // 返回 1

```

提示：

• 1 <= persons.length <= 5000

• times.length == persons.length

• 0 <= persons[i] < persons.length

• 0 <= times[i] <= 10^9

• times 是一个严格递增的有序数组

• times[0] <= t <= 10^9

• 每个测试用例最多调用 10^4 次 q

1712. 将数组分成三个子数组的方案数

我们称一个分割整数数组的方案是 好的 ，当它满足：

• 数组被分成三个 非空 连续子数组，从左至右分别命名为 left ， mid ， right 。

• left 中元素和小于等于 mid 中元素和，mid 中元素和小于等于 right 中元素和。

给你一个 非负 整数数组 nums ，请你返回 好的 分割 nums 方案数目。由于答案可能会很大，请你将结果对 10^9 + 7 取余后返回。

示例 1：

```txt

输入：nums = [1,1,1]

输出：1

解释：唯一一种好的分割方案是将 nums 分成 [1] [1] [1] 。

```

示例 2：

```txt

输入：nums = [1,2,2,2,5,0]

输出：3

解释：nums 总共有 3 种好的分割方案：

[1] [2] [2,2,5,0]

[1] [2,2] [2,5,0]

[1,2] [2,2] [5,0]

```

示例 3：

```txt

输入：nums = [3,2,1]

输出：0

解释：没有好的分割方案。

```

提示：

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

• 0 <= nums[i] <= 10^4