n数选数和为倍数

从n个数中选出几个数使和为n的倍数(鸽巢原理)

Origin

Daimayuan Online Judge - 456

题意：

给定一个长度为 \(n(n \le {10^5})\) 的数组，你需要从里面选择一些数，使得其和为 \(n\) 的倍数。

思路：

我们可以计算前缀和，其中 \(pre[0] = 0,pre[1] = a[1],pre[2] = a[1] + a[2]\)。

对于前缀和数组来说，一共有 \(n+1\) 个数，而我们关心的是 \(n\) 的倍数，所以我们都模上 \(n\) 。

而模 \(n\) 的值的可能只有 \([0,n - 1]\) 种，那么这 \(n+1\) 个数中一个存在两个相同的数。

• 如果后 \(n\) 个数里面有 \(0\) 的话，可以和 \(pre[0]\) 匹配。

• 如果后 \(n\) 个数里面没有 \(0\) 的话，那就是 \(n\) 个位置里面塞 \(n-1\) 种数，必然有一个重复的。

可以发现，我们一定能找到一种情况。

Code

int a[MAXN], pre[MAXN], n;
void slove() {
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> a[i];
	for (int i = 1; i <= n; i++)(pre[i] = pre[i - 1] + a[i]) %= n;
	map<int, int>mp; mp[0] = 0;
	for (int i = 1; i <= n; i++) {
		pre[i] %= n;
		if (mp.count(pre[i])) {
			cout << i - mp[pre[i]] << endl;
			for (int j = mp[pre[i]] + 1; j <= i; j++)cout << j << " ";
			cout << endl;
			return;
		}
		mp[pre[i]] = i;
	}
}