fork()==0世界线变动

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 只包含小写英文字母和空格 ' ' 。

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

2954. 统计感冒序列的数目

给你一个整数 n 和一个下标从 0 开始的整数数组 sick ，数组按 升序 排序。

有 n 位小朋友站成一排，按顺序编号为 0 到 n - 1 。数组 sick 包含一开始得了感冒的小朋友的位置。如果位置为 i 的小朋友得了感冒，他会传染给下标为 i - 1 或者 i + 1 的小朋友，前提 是被传染的小朋友存在且还没有得感冒。每一秒中， 至多一位 还没感冒的小朋友会被传染。

经过有限的秒数后，队列中所有小朋友都会感冒。感冒序列 指的是 所有 一开始没有感冒的小朋友最后得感冒的顺序序列。请你返回所有感冒序列的数目。

由于答案可能很大，请你将答案对 10^9 + 7 取余后返回。

注意，感冒序列 不 包含一开始就得了感冒的小朋友的下标。

示例 1：

```txt

输入：n = 5, sick = [0,4]

输出：4

解释：一开始，下标为 1 ，2 和 3 的小朋友没有感冒。总共有 4 个可能的感冒序列：

• 一开始，下标为 1 和 3 的小朋友可以被传染，因为他们分别挨着有感冒的小朋友 0 和 4 ，令下标为 1 的小朋友先被传染。

然后，下标为 2 的小朋友挨着感冒的小朋友 1 ，下标为 3 的小朋友挨着感冒的小朋友 4 ，两位小朋友都可以被传染，令下标为 2 的小朋友被传染。

最后，下标为 3 的小朋友被传染，因为他挨着感冒的小朋友 2 和 4 ，感冒序列为 [1,2,3] 。

• 一开始，下标为 1 和 3 的小朋友可以被传染，因为他们分别挨着感冒的小朋友 0 和 4 ，令下标为 1 的小朋友先被传染。

然后，下标为 2 的小朋友挨着感冒的小朋友 1 ，下标为 3 的小朋友挨着感冒的小朋友 4 ，两位小朋友都可以被传染，令下标为 3 的小朋友被传染。

最后，下标为 2 的小朋友被传染，因为他挨着感冒的小朋友 1 和 3 ，感冒序列为 [1,3,2] 。

• 感冒序列 [3,1,2] ，被传染的顺序：[0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] 。

• 感冒序列 [3,2,1] ，被传染的顺序：[0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] 。

```

示例 2：

```txt

输入：n = 4, sick = [1]

输出：3

解释：一开始，下标为 0 ，2 和 3 的小朋友没有感冒。总共有 3 个可能的感冒序列：

• 感冒序列 [0,2,3] ，被传染的顺序：[0,1,2,3] => [0,1,2,3] => [0,1,2,3] => [0,1,2,3] 。

• 感冒序列 [2,0,3] ，被传染的顺序：[0,1,2,3] => [0,1,2,3] => [0,1,2,3] => [0,1,2,3] 。

• 感冒序列 [2,3,0] ，被传染的顺序：[0,1,2,3] => [0,1,2,3] => [0,1,2,3] => [0,1,2,3] 。

```

提示：

• 2 <= n <= 10^5

• 1 <= sick.length <= n - 1

• 0 <= sick[i] <= n - 1

• sick 按升序排列。

100126. 重新排列后包含指定子字符串的字符串数目

给你一个整数 n 。

如果一个字符串 s 只包含小写英文字母，且 将 s 的字符重新排列后，新字符串包含 子字符串 "leet" ，那么我们称字符串 s 是一个 好 字符串。

比方说：

• 字符串 "lteer" 是好字符串，因为重新排列后可以得到 "leetr" 。

• "letl" 不是好字符串，因为无法重新排列并得到子字符串 "leet" 。

请你返回长度为 n 的好字符串 总 数目。

由于答案可能很大，将答案对 10^9 + 7 取余 后返回。

子字符串 是一个字符串中一段连续的字符序列。

示例 1：

```txt

输入：n = 4

输出：12

解释：总共有 12 个字符串重新排列后包含子字符串 "leet" ："eelt" ，"eetl" ，"elet" ，"elte" ，"etel" ，"etle" ，"leet" ，"lete" ，"ltee" ，"teel" ，"tele" 和 "tlee" 。

```

示例 2：

```txt

输入：n = 10

输出：83943898

解释：长度为 10 的字符串重新排列后包含子字符串 "leet" 的方案数为 526083947580 。所以答案为 526083947580 % (109 + 7) = 83943898 。

```

提示：

• 1 <= n <= 10^5

2867. 统计树中的合法路径数目

给你一棵 n 个节点的无向树，节点编号为 1 到 n 。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示节点 ui 和 vi 在树中有一条边。

请你返回树中的 合法路径数目 。

如果在节点 a 到节点 b 之间 恰好有一个 节点的编号是质数，那么我们称路径 (a, b) 是 合法的 。

注意：

• 路径 (a, b) 指的是一条从节点 a 开始到节点 b 结束的一个节点序列，序列中的节点 互不相同 ，且相邻节点之间在树上有一条边。

• 路径 (a, b) 和路径 (b, a) 视为 同一条 路径，且只计入答案 一次 。

示例 1：

```txt

输入：n = 5, edges = [[1,2],[1,3],[2,4],[2,5]]

输出：4

解释：恰好有一个质数编号的节点路径有：

• (1, 2) 因为路径 1 到 2 只包含一个质数 2 。

• (1, 3) 因为路径 1 到 3 只包含一个质数 3 。

• (1, 4) 因为路径 1 到 4 只包含一个质数 2 。

• (2, 4) 因为路径 2 到 4 只包含一个质数 2 。

只有 4 条合法路径。

```

示例 2：

```txt

输入：n = 6, edges = [[1,2],[1,3],[2,4],[3,5],[3,6]]

输出：6

解释：恰好有一个质数编号的节点路径有：

• (1, 2) 因为路径 1 到 2 只包含一个质数 2 。

• (1, 3) 因为路径 1 到 3 只包含一个质数 3 。

• (1, 4) 因为路径 1 到 4 只包含一个质数 2 。

• (1, 6) 因为路径 1 到 6 只包含一个质数 3 。

• (2, 4) 因为路径 2 到 4 只包含一个质数 2 。

• (3, 6) 因为路径 3 到 6 只包含一个质数 3 。

只有 6 条合法路径。

```

提示：

• 1 <= n <= 10^5

• edges.length == n - 1

• edges[i].length == 2

• 1 <= ui, vi <= n

• 输入保证 edges 形成一棵合法的树。

1240. 铺瓷砖

你是一位施工队的工长，根据设计师的要求准备为一套设计风格独特的房子进行室内装修。

房子的客厅大小为 n x m，为保持极简的风格，需要使用尽可能少的 正方形 瓷砖来铺盖地面。

假设正方形瓷砖的规格不限，边长都是整数。

请你帮设计师计算一下，最少需要用到多少块方形瓷砖？

示例 1：

```txt

输入：n = 2, m = 3

输出：3

解释：3 块地砖就可以铺满卧室。

 2 块 1x1 地砖 1 块 2x2 地砖

```

示例 2：

```txt

输入：n = 5, m = 8

输出：5

```

示例 3：

```txt

输入：n = 11, m = 13

输出：6

```

提示：

• 1 <= n <= 13

• 1 <= m <= 13