ACM程序设计选修课——1058: Lucky Sequence（思考）

1058: Lucky Sequence

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 52 Solved: 6
[ Submit][ Status][ Web Board]

Description

Edward 得到了一个长度为 N 的整数序列，他想找出这里面有多少个“幸运的”
连续子序列。一个连续子序列被称为“幸运的”，当且仅当该子序列内的整数之
和恰好是 K 的整数倍数。他请求你写一个程序来计算他喜欢的连续子序列个数.

Input

输入第一行是一个整数 T，表示有 T 组数据。
每组数据第一行是两个整数 N (1 <= N <= 10^6), K (1 <= K <= 10^9)。
接下来的一行包含 N 个整数 Ai (|Ai| <= 10^9)。

Output

对于每组测试数据，输出一行仅包含一个整数，表示 Edward 喜欢的连续子序
列数量。

Sample Input

2
5 3
1 2 3 4 1
6 2
1 2 1 2 1 2

Sample Output

4
9

刚开始也不会，问了学长、大神，说用map+枚举一个端点值，想了一个早上得出一个计算公式

设Sum[x]为下标1~x的元素和，那么Sum[I~r]=Sum[r]-Sum[l-1]；例如Sum[3~6]=Sum[6]-Sum[2]（Sum[3-1]）。然后题目要求的是Sum[q~p]%k==0，把前面拆掉变成（ Sum[p] - Sum[q-1] ）%k==0，再拆开移项，得到Sum[p]%k==Sum[q-1] %k；

1、若取模数不为0，则需要找一个一样的来形成上述等式，因此sum_cnt=(second+second-1)÷2；

2、若取模数为0，则除了1的条件，自身对K取模也是0也要算进去，因此为(second+second-1)÷2+second=(second+second+1)÷2（这条没用到，因为后面直接加回来就可以了）

为了不每次都%k，用map记录时直接把first改为%k之后的结果，这题一个坑点就是负数的问题，例如4%3==1，-5%3==1，而不是-2或者2，因此要用（x%k+k）%k这个公式来将负数取模转换成对应的题目所要求的正数。而不是简单的abs或fabs（为此WA了好几次）。还有数据都用long long，全为int也是WA。

代码：

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
int main (void)
{
	int t,i,n;
	LL temp,ans,k,tsum,q;
	scanf("%d",&t);
	while (t--)
	{
		map<LL,LL>mist;//记录某一个取模结果对应的出现次数
		scanf("%d%lld",&n,&k);
		tsum=0;
		ans=0;
		mist[0]=0;
		for (i=1; i<=n; i++)
		{
			scanf("%lld",&temp);
			tsum+=temp;
			mist[(tsum%k+k)%k]++;
		}	
		map<LL,LL>::iterator it;
		for (it=mist.begin(); it!=mist.end(); it++)
		{
			k=it->second;
			ans=ans+(k*(k-1))/2;
		}
		ans=ans+mist[0];
		printf("%lld\n",ans);
	}
	return 0;
}

秒客网