题意分析

我们需要从给定的 $N$ 个正整数中选出一个非空子集，使得这个子集的和是 $N$ 的倍数。如果存在多个解，输出任意一个即可；如果没有解，输出 $0$。

关键点：

1. 子集和是 $N$ 的倍数，即 $\text{sum} \equiv 0 \ (\text{mod}\ N)$。
2. 子集可以是任意大小（$1 \leq \text{size} \leq N$）。
3. 数字可能重复，但子集可以任意选取（不要求连续）。

解题思路

1. 暴力法（不可行）

• 直接枚举所有可能的子集，检查它们的和是否是 $N$ 的倍数。
• 时间复杂度 $O(2^N)$，在 $N \leq 10000$ 时无法通过。

2. 动态规划（不可行）

• 定义 $dp[i][j]$ 表示前 $i$ 个数是否能组成和模 $N$ 余 $j$。
• 时间和空间复杂度 $O(N^2)$，在 $N \leq 10000$ 时仍然不可行。

3. 鸽巢原理 + 前缀和（最优解法）

核心观察：

• 计算前缀和模 $N$，即： [ S[i] = (a_1 + a_2 + \dots + a_i) \mod N ]
• 如果某个 $S[i] = 0$，则前 $i$ 个数的和就是 $N$ 的倍数，直接输出。
• 否则，根据鸽巢原理，$S[1..N]$ 共有 $N$ 个值，但模 $N$ 的结果只有 $0,1,\dots,N-1$ 共 $N$ 种可能。
  • 如果 $S[i] = S[j]$（$i < j$），则 $a_{i+1} + a_{i+2} + \dots + a_j \equiv 0 \ (\text{mod}\ N)$，即这段子数组的和是 $N$ 的倍数。
• 结论：必然存在解，并且可以在 $O(N)$ 时间内找到。

实现步骤

1. 计算前缀和模 $N$：
   • 初始化 $S[0] = 0$。
   • 遍历数组，计算 $S[i] = (S[i-1] + a_i) \mod N$。
2. 检查是否有 $S[i] = 0$：
   • 如果有，直接输出前 $i$ 个数。
3. 如果没有 $S[i] = 0$，则必有重复余数：
   • 使用哈希表记录每个余数第一次出现的位置。
   • 如果某个余数再次出现，则取出 $[i+1, j]$ 这段子数组作为解。
4. 输出解：
   • 输出子数组的大小和具体数字。

代码实现

#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

void findSubset(const vector<int>& numbers, int N) {
    vector<int> modIndices(N, -1); // 记录余数对应的索引
    int currentSum = 0;

    for (int i = 0; i < N; ++i) {
        currentSum = (currentSum + numbers[i]) % N;
        
        // 如果当前余数为0，找到解
        if (currentSum == 0) {
            cout << i + 1 << endl;
            for (int j = 0; j <= i; ++j) {
                cout << numbers[j] << endl;
            }
            return;
        }
        
        // 如果这个余数之前出现过，找到解
        if (modIndices[currentSum] != -1) {
            int start = modIndices[currentSum] + 1;
            cout << i - start + 1 << endl;
            for (int j = start; j <= i; ++j) {
                cout << numbers[j] << endl;
            }
            return;
        }
        
        modIndices[currentSum] = i;
    }
    
    // 没有找到解
    cout << 0 << endl;
}

int main() {
    int N;
    cin >> N;
    
    vector<int> numbers(N);
    for (int i = 0; i < N; ++i) {
        cin >> numbers[i];
    }
    
    findSubset(numbers, N);
    
    return 0;
}