[CSP-S模拟测试]:Set（随机化）

题目描述

你手上有$N$个非负整数，你需要在这些数中找出一个非空子集，使得它的元素之和能被$N$整除。如果有多组合法方案，输出任意一组即可。
注意：请使用高效的输入输出方式避免输入输出耗时过大。

输入格式

第一行一个整数$N$，代表数字个数。
接下来一行$N$个数，代表你手上的数。

输出格式

如果无解，输出$-1$。
否则，第一行输出一个整数$M$，代表你选择的数的个数。
接下来一行$M$个数，代表你选中元素的下标，这$M$个数必须两两不同。

样例

样例输入：

3
4 6 10

样例输出：

1
2

数据范围与提示

对于$20\%$的数据，$N\leqslant 20$。
对于$50\%$的数据，$N\leqslant 1,000$。
对于$100\%$的数据，$N\leqslant 1,000,000$，数字大小不超过${10}^9$。

题解

再一次没有打整洁……

有这样一个结论，对于一个序列，如果有一段的和$\mod N$为$0$，那么无论怎么打乱序列都会存在这么一段；如果没有，无论怎么打乱还是没有。

具体为什么我也不会证明，考场上用这个结论$A$掉这道题的也说不上来（我都不知道他们是怎么$A$的……）

所以我们可以记录一下每个模数出现的位置，如果已经出现过了直接输出这一段就好了。

然而考场上我并没有这么做，$random_shuffle$随机打乱序列，然后看前缀和$\mod N$是否为$0$，如果有则输出这些数。

当时以为自己只能拿$20$分，于是打了一个比正解还难搞的$50$分的$DP$，考完之后……

我的天！！！$Accepted$，当时就懵了……

所以考场上乱搞还是有很大帮助的。

时间复杂度：$\Theta($玄学$)$（实际上挺小的）。

期望得分：$100$分（其实考场上以为只有$20$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int n;

pair<int,int> a[1000001];

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&a[i].first);

		a[i].first%=n;

		a[i].second=i;

		if(!a[i].first){printf("1\n%d",i);return 0;}

	}

	srand(time(NULL));

	while(1)

	{

		random_shuffle(a+1,a+n+1);

		int sum=0;

		for(int i=1;i<=n;i++)

		{

			sum=(sum+a[i].first)%n;

			if(!sum)

			{

				printf("%d\n",i);

				for(int j=1;j<=i;j++)

					printf("%d ",a[j].second);

				return 0;

			}

		}

	}

	return 0;

}

rp++

巴特西