题目链接

模意义下最大子序列和

题目描述

给定一个含有 () 个正整数的数组 以及一个正整数模数 ()。你可以任选若干下标递增的元素构成一个子序列（允许选择空序列）。设所选元素之和为 ，求 的最大可能值。

解题思路

这是一个求解所有子序列和模 的最大值问题。

1. 算法选择

本题的关键在于数据范围：数组长度 非常小（），而模数 和数组元素 可能非常大。

  • 的动态规划解法：由于 可以达到 ，时间和空间复杂度都无法接受。
  • 的搜索解法：由于 ，，这是一个非常小的计算量。因此，我们可以通过枚举所有可能的子序列来解决问题。

深度优先搜索（DFS）是实现子序列枚举的经典方法。

2. 深度优先搜索 (DFS) 流程

我们可以定义一个递归函数，例如 dfs(index, current_sum_mod_m)，来探索所有可能性。

  • 函数参数：

    • index：当前正考虑数组 a 中的第 index 个元素。
    • current_sum_mod_m：到目前为止，已选子序列的元素和对 取模后的值。

  • 递归逻辑： 在 dfs(index, current_sum_mod_m) 中，对于元素 a[index]，我们有两个选择：

    1. 不选择 a[index]： 子序列和不变，我们继续处理下一个元素。递归调用 dfs(index + 1, current_sum_mod_m)。
    2. 选择 a[index]： 新的子序列和为 (current_sum_mod_m + a[index]) % m。我们继续处理下一个元素。递归调用 dfs(index + 1, (current_sum_mod_m + a[index]) % m)。

  • 递归终止条件： 当 index == n 时，说明我们已经对所有元素做出了选择，形成了一个完整的子序列。此时的 current_sum_mod_m 就是这个子序列的和模 的值。我们将这个值记录下来。

  • 收集与去重： 我们可以使用一个 set (或 HashSet) 来存储所有在递归终止时得到的 current_sum_mod_m。set 可以自动处理重复的和值。

  • 最终答案： DFS结束后，set 中存储了所有可能的子序列和模 的值。我们需要找到这个 set 中的最大元素。不要忘记，空子序列（和为0）也是一个合法的选项，所以需要将 0 也考虑在内。

代码

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int n;
long long m;
vector<long long> a;
set<long long> possible_sums;

void dfs(int index, long long current_sum) {
    if (index == n) {
        possible_sums.insert(current_sum);
        return;
    }

    // 不选择 a[index]
    dfs(index + 1, current_sum);

    // 选择 a[index]
    dfs(index + 1, (current_sum + a[index]) % m);
}

int main() {
    cin >> n >> m;
    a.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 初始调用，代表从第0个元素开始，当前和为0
    dfs(0, 0);

    // set 中最后一个元素即为最大值
    if (possible_sums.empty()) {
        cout << 0 << endl;
    } else {
        cout << *possible_sums.rbegin() << endl;
    }

    return 0;
}

import java.util.Scanner;
import java.util.HashSet;
import java.util.Collections;

public class Main {
    private static int n;
    private static long m;
    private static long[] a;
    private static HashSet<Long> possibleSums;

    private static void dfs(int index, long currentSum) {
        if (index == n) {
            possibleSums.add(currentSum);
            return;
        }

        // 不选择 a[index]
        dfs(index + 1, currentSum);

        // 选择 a[index]
        dfs(index + 1, (currentSum + a[index]) % m);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextLong();
        a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        possibleSums = new HashSet<>();
        dfs(0, 0);

        if (possibleSums.isEmpty()) {
            System.out.println(0);
        } else {
            System.out.println(Collections.max(possibleSums));
        }
    }
}

import sys

# 对于深度较深的递归，可能需要增加递归深度限制
# 在本题 n <= 15 的情况下，通常不是必需的
# sys.setrecursionlimit(20)

n, m = 0, 0
a = []
possible_sums = set()

def dfs(index, current_sum):
    if index == n:
        possible_sums.add(current_sum)
        return

    # 不选择 a[index]
    dfs(index + 1, current_sum)

    # 选择 a[index]
    dfs(index + 1, (current_sum + a[index]) % m)

def solve():
    global n, m, a
    try:
        line = input()
        if not line: return
        n, m = map(int, line.split())
        
        line = input()
        if not line: return
        a = list(map(int, line.split()))
    except (IOError, ValueError):
        return

    possible_sums.clear()
    dfs(0, 0)
    
    if not possible_sums:
        print(0)
    else:
        print(max(possible_sums))

solve()

算法及复杂度

  • 算法：深度优先搜索（DFS）、回溯法

  • 时间复杂度：。对于数组中的 个元素，每个元素都有“选”和“不选”两种状态，总共构成 种不同的子序列。DFS树有 个节点，所以复杂度是 。

  • 空间复杂度：。在最坏情况下，可能会产生 个不同的子序列和，我们需要使用 set 来存储它们。同时，递归调用栈的深度为 ，但存储结果的空间占主导。