Note: This article is available in Chinese only. 本文暂无英文版本。
View original
http://poj.org/problem?id=2356
题意：有 n 个数，从中选取若干个（1..n），和能被 n 整除。问是否有解，无解输出 0，有解的话，输出个数以及选择的 a[i]（不是 i）。
由抽屉原理可知一定有解：
做一个带模的前缀和 sum[i]=(sum[i-1]+a[i])%n
n个数，sum[i]最多有n种。
如果某个sum[i]为0，那么表示从1到i的和能被n整除。
如果所有的 sum[i] 不为 0，那么一共有 n 个 sum[i]、n-1 个值（1..n-1），一定有 sum[i] == sum[j]（i <= j）。
那么a[i]到a[j]的和一定能被n整除。
代码实现
1/*************************************************************************
2 > File Name: code/poj/2356.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年08月21日 星期五 13时43分41秒
6 ************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#define y0 abc111qqz
21#define y1 hust111qqz
22#define yn hez111qqz
23#define j1 cute111qqz
24#define tm crazy111qqz
25#define lr dying111qqz
26using namespace std;
27#define REP(i, n) for (int i=0;i<int(n);++i)
28typedef long long LL;
29typedef unsigned long long ULL;
30const int inf = 0x3f3f3f3f;
31const int N=2E4+7;
32int a[N];
33int sum[N];
34int n;
35int p[N];
36int main()
37{
38 scanf("%d",&n);
39 sum[0]= 0;
40 for ( int i = 1 ; i <= n ; i++){
41 scanf("%d",&a[i]);
42 sum[i] = (sum[i-1] + a[i])%n;
43 }
44 memset(p,0,sizeof(p));
45 for ( int i = 1 ; i <= n ; i++){
46 if (sum[i]==0){
47 printf("%d\n",i);
48 for ( int j = 1 ; j <= i ; j++){
49 printf("%d\n",j);
50 }
51 break;
52 }
53 if (p[sum[i]]){
54 // cout<<"111qqz"<<endl;
55 printf("%d\n",i-p[sum[i]]);
56 for ( int j = p[sum[i]]+1 ; j <= i ; j++){
57 printf("%d\n",j);
58 }
59 break;
60 }
61 p[sum[i]] = i;
62
63 }
64
65 return 0;
66}