k倍区间(抽屉原理O(n))

标题： k倍区间 给定一个长度为N的数列，A1, A2, ... AN，如果其中一段连续的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍数，我们就称这个区间[i, j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗？ 输入 ----- 第一行包含两个整数N和K。(1 <= N, K <= 100000) 以下N行每行包含一个整数Ai。(1 <= Ai <= 100000) 输出 ----- 输出一个整数，代表K倍区间的数目。 例如， 输入： 5 2 1 2 3 4 5 程序应该输出： 6 资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 2000ms 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。 注意： main函数需要返回0; 只使用ANSI C/ANSI C++ 标准; 不要调用依赖于编译环境或操作系统的特殊函数。 所有依赖的函数必须明确地在源文件中 #include <xxx> 不能通过工程设置而省略常用头文件。 提交程序时，注意选择所期望的语言类型和编译器类型。 求出前缀和然后取模,范围0~k-1之间。 用ct数组记录之前i出现过几次。 pos数组记录i是否出现过，且第一次出现的位置 抽屉原理就是如果sum[i]=sum[j],那么[i+1,j]这一段必定能被k整除。 样例: 1 2 3 4 5 化成 1 1 0 0 1,例如sum[2]到sum[5],1,0,0,1,由于sum[2]==sum[5]，那么(pos[sum[2]]+1,pos[sum[5]])这一段连续区间和被k整除，具体可以看抽屉原理。 #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cctype> #include<cmath> #include<ctime> #include<string> #include<stack> #include<deque> #include<queue> #include<list> #include<set> #include<map> #include<cstdio> #include<limits.h> #define MOD 1000000007 #define fir first #define sec second #define fin freopen("/home/ostreambaba/文档/input.txt", "r", stdin) #define fout freopen("/home/ostreambaba/文档/output.txt", "w", stdout) #define mes(x, m) memset(x, m, sizeof(x)) #define Pii pair<int, int> #define Pll pair<ll, ll> #define INF 1e9+7 #define inf 0x3f3f3f3f #define Pi 4.0*atan(1.0) #define lowbit(x) (x&(-x)) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 typedef long long ll; typedef unsigned long long ull; const double eps = 1e-9; const int maxn = 1e7; using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*f; } int sum[maxn],kt[maxn],pos[maxn],ct[maxn]; int main(){ //freopen("/home/ostreambaba/文档/input.txt", "r", stdin); int n,k; sum[0]=0; int ans=0; fill(pos,pos+n+1,-1); n=read(),k=read(); for(int i=1;i<=n;++i){ int t=read(); sum[i]=(sum[i-1]+t)%k; } for(int i=1;i<=n;++i){ if(sum[i]==0){ ++ans; pos[sum[i]]=i; }if(pos[sum[i]]==-1){ pos[sum[i]]=i; ct[sum[i]]++; }else{ ans+=ct[sum[i]]; ct[sum[i]]++; } } printf("%d\n",ans); return 0; }