sequence|sequence.in|sequence.out
题目描述：
给定一个整数K和长为N的数列{Ai}，求有多少个子串（不含空串）的和为K的倍数。（在这里子串表示{A[i]..A[j]}，i<=j）
输入格式：
共两行
第一行两个整数N,K
第二行N个整数表示数列{Ai}
输出格式：
一行一个整数表示满足条件的子串的个数
样例输入：
6 3
1 2 6 3 7 4
样例输出：
7
数据范围：
20% N<=100
对另外20% K<=100
对所有数据N<=500000 K<=500000
保证输入数据中所有数都能用longint保存
一定注意mod为负数的情况。
#include<iostream>#include<cstdio>#include<cstring>using namespace std;#define PROB "sequence"#define MAXN 550000#ifdef unix#define LL "%lld"#else #define LL "I64d"#endiftypedef long long qword;int num[MAXN];int sum[MAXN];int tot[MAXN];int main(){ freopen(PROB".in","r",stdin); freopen(PROB".out","w",stdout); int n,m; int i,j; scanf("%d%d",&n,&m); for (i=1;i<=n;i++) { scanf("%d",num+i); sum[i]=(sum[i-1]+num[i])%m; sum[i]=(sum[i]+m)%m; } qword ans=0; for (i=0;i<=n;i++) { ans+=tot[sum[i]]; tot[sum[i]]++; } printf(LL"\n",ans);}
转载于:https://www.cnblogs.com/mhy12345/p/3837314.html
