选数

题目描述：

给你n个数字，你需要找出若干个数字，使得这些数字的和对n取余后等于0，每个下标最多只能取一次

输出长度和选的数字的下标

思路：

很巧妙的一个鸽巢原理

计sum[i]是前缀和，sum[i]对n取模，则sum[0]到sum[n]一定有n+1个数字，根据鸽巢原理，一定存在两个取余后相同的数字，根据前缀和的性质，则可以满足这个区间的数字和%n=0

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];
vector<int>v[MAX];
void work(){
    cin >> n;
    v[0].push_back(0);
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];
        (tr[i] += tr[i - 1])%=n;
        v[tr[i]].push_back(i);
    }
    for(int i = 0; i < n; ++i){
        if(v[i].size() > 1){
            cout << v[i][1] - v[i][0] << endl;
            for(int j = v[i][0] + 1; j <= v[i][1]; ++j)cout << j << ' ';
            cout << endl;
            return;
        }
    }
}


int main(){
    io;
    work();
    return 0;
}