HUST team contest #2 C Divisible Subsequences ||poj 3844 (剩余类)
算是签到帖，竟然卡住了。
我数学还是太差了。。
然后去找题解。。竟然看不懂！
我数学真的有这么差嘛。。。
然后多亏了队友 @zcy 妹子的讲解。。
其实很好理解啊。。。
不过数到底还是数学太差了==
今天七夕，废话有点多==
这道题的题意是，找序列中连续的一段，使得和 可以整除d
我们观察到数列中的数的范围是1..1 000 000 000 的
而d只有1 000 000
我们考虑余数相同，读入的时候就可以直接先 % 掉 d
因为只会和余数有关。
我们可以先处理出来一个前缀和数组sum[i]，表示前i个元素的和。
如果有一段序列从a[i] 到 a[j] 满足题意
根据题意那么这段序列的和一定%d=0
a[i] 到 a[j]的和为 sum[j]-sum[i-1]
也就是(sum[j]-sum[i-1] )%d==0
也就是sum[j] 和 sum[i-1] 关于 d 同余
如果我们在处理得到前缀和的时候就%dshuxue
那么就是sum[j]==sum[i-1]
所以我只要对于d的每一个剩余类有多少个统计出来。
然后对于每个剩余类，只需要任意取出两个，就是一种答案。
需要注意的是如果只有一个0，也是一种答案。
我们可以定义sum[i] = 0
还有一个需要注意的是要开long long
1/* ***********************************************
2Author :111qqz
3Created Time :2016年02月29日 星期一 21时20分01秒
4File Name :code/poj/3844.cpp
5************************************************ */
6
7#include<iostream>
8#include<iomanip>
9#include<cstdio>
10#include<algorithm>
11#include<cmath>
12#include<cstring>
13#include<string>
14#include<map>
15#include<set>
16#include<queue>
17#include<vector>
18#include<stack>
19#define y0 abc111qqz
20#define y1 hust111qqz
21#define yn hez111qqz
22#define j1 cute111qqz
23#define tm crazy111qqz
24#define lr dying111qqz
25using namespace std;
26#define REP(i, n) for (int i=0;i<int(n);++i)
27typedef long long LL;
28typedef unsigned long long ULL;
29const int inf = 0x7fffffff;
30const int N=1E6+7;
31int sum[50005];
32LL p[N];
33
34void solve ()
35{
36 int d,n;
37 int x;
38 memset(p,0,sizeof(p));
39 sum[0] = 0;
40 p [0] = 1;
41 for ( int i = 1 ; i <= n ; i++){
42 scanf("%d",&x);
43 sum[i] = (sum[i-1] + x) % d;
44 p[sum[i]]++;
45 }
46 LL ans = 0 ;
47 for ( int i = 0 ; i < d ; i++){
48 if (p[i]>0){
49 ans = ans + p[i]*(p[i]-1)/2;
50 }
51 }
52 cout<<ans<<endl;
53}
54int main()
55{
56 int T;
57 cin>>T;
58 while (T--){
59 solve();
60 }
61 return 0;
62}