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;
	}
}