吃++中一堆数的子序列

题目描述：

给定一个长度为n的正整数序列 a1,a2,…,an，你需要选出一个非空子序列，使得这个子序列中的数的乘积模 109+7 的值最大。

数据范围：1≤n≤105，1≤ai≤103。

样例：

输入：

3

1 2 3

输出：

6

输入：

4

1 2 3 4

输出：

24

算法1：

(暴力枚举) $O(n^2)$

枚举所有子序列，计算乘积并取模，记录最大值。

时间复杂度

枚举子序列需要 $O(n^2)$，计算乘积需要 $O(n)$，所以总时间复杂度为 $O(n^3)$。

C++ 代码

算法2：

(贪心) $O(n)$

由于模数为质数，我们可以使用费马小定理求乘法逆元。

对于每个数，我们可以先把它分解质因数，然后对于每个质因子，我们可以计算出它在所有子序列中出现的次数，这个次数是 $2^n-1$，其中 $n$ 是这个质因子出现的次数。我们可以使用快速幂计算 $2^n-1$，然后乘上这个质因子，最后再将所有质因子的积取模，就得到了最大乘积。

时间复杂度

每个数需要分解质因数，时间复杂度为 $O(\sqrt{n}\log n)$，计算每个质因子的次数需要用到快速幂，时间复杂度为 $O(\log p)$，总时间复杂度为 $O(n\sqrt{n}\log n)$。

C++ 代码

相关问题

已知在一维数组a[m+n]中一次存放两个线性表a和b编写一个函数,将数组中两个顺序表

假设给定的一维数组 a[m+n] 存放了两个顺序表 a 和 b，我们可以使用如下的方法将这两个顺序表分开：
1. 定义一个新的数组 c[m+n] 来存放结果。
2. 将数组 a 中的元素逐个复制到数组 c 中，即将 a 的元素从下标 0 到 m-1 复制到 c 的下标 0 到 m-1。
3. 将数组 b 中的元素逐个复制到数组 c 中，即将 b 的元素从下标 0 到 n-1 复制到 c 的下标 m 到 m+n-1。
4. 返回数组 c，即为将数组 a 和 b 分开的结果。

下面是一个示例代码的实现：

def separate_lists(a, b, m, n):
    c = [0] * (m + n)
    for i in range(m):
        c[i] = a[i]
    for i in range(n):
        c[m+i] = b[i]
    return c

这样，通过调用 `separate_lists(a, b, m, n)` 函数，就可以将数组 a 和 b 分开存放，返回值即为结果数组 c。

python修改二维列表中一列数

要修改二维列表中的一列数，可以使用循环遍历每一行，并且在每一行中修改对应的列数。下面是一个示例代码：

# 定义一个二维列表
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

# 要修改的列数
col_index = 1

# 修改第 col_index 列的值为新值 new_value
new_value = 10
for row in matrix:
    row[col_index] = new_value

# 输出修改后的二维列表
print(matrix)

输出结果为：

[[1, 10, 3], [4, 10, 6], [7, 10, 9]]

以上代码中，我们遍历了二维列表的每一行，并且将第 `col_index` 列的值修改为了 `new_value`。最后输出修改后的二维列表。