撰写问题描述
给定一个长度为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)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)
输出格式
输出一个整数，代表K倍区间的数目。
样例输入
5 2
1
2
3
4
5
1
2
3
4
5
样例输出
6
- 题解
- 有些傻子一看2s就开始想屁吃
- 区间问题，必然是从简到繁进行考虑
- 对于区间问题，我首先考虑的是 前缀和数组、单调栈、单调队列等初级算法与数据结构
- 然后再综合题意考虑RMQ、线段树、分块、分点、分治（时间域与值域）以及treap等树形结构
- 而这题，不需要可持久化、修改等操作，初步排序线段树等较为复杂的数据结构
- 再一看不具有区间重排的性质，分块与分点可以初步排除
- 对于分治，显然不符合这道题的要求，因为这题没有可以区间合并的性质
- 那么考虑最简单的方法实现
- 先考虑单调性，不具有特殊的单调性
- 考虑前缀和，暴力方法O(n^2)超时
- 再思考题目种的显性关键点——k倍，以及两个位置前缀和之间的隐性关键点——连续
- 我们可以先将所有前缀和取余，而中间段的大小是通过两段之间相减得来的
- 换言之，当取余后的sum[i]与sum[j]相等的时候，中间段的和就可以被k整除
- 所以我们统计所有被k余后相同的前缀和，显然余数相同的k个前缀和可以得到（1+2…+k-1）个符合答案的段，所以每次找到相同的时候++就行了
- 最后，0可以自己忍受孤独并且最后的数可以和我一样大(长？哈哈哈)，所以用long long准没错啦
- 代码
-
#include<algorithm> #include <iostream> #include <fstream> #include <cstdlib> #include <cstring> #include <cassert> #include <cstdio> #include <vector> #include <string> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> using namespace std; #define P(a,b,c) make_pair(a,make_pair(b,c)) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,a,n) for (int i=n;i>=a;i--) #define CLR(vis) memset(vis,0,sizeof(vis)) #define MST(vis,pos) memset(vis,pos,sizeof(vis)) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef pair<int,pair<int,int> >pii; typedef long long ll; typedef unsigned long long ull; const ll mod = 1000000007; const int INF = 0x3f3f3f3f; ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; } template<class T>inline void gmax(T &A, T B) { (A<B)&&(A=B);//if(B>A)A=B; } template<class T>inline void gmin(T &A, T B) { (A>B)&&(A=B);//if(B<A)A=B; } template <class T> inline bool scan(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; //EOF while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } inline void outt(int x) { if(x>9) outt(x/10); putchar(x%10+'0'); } const int maxn=1e6+10; int a[maxn]; int b[maxn]; int main(){ int n,k; cin>>n>>k; rep(i,1,n)scan(a[i]),a[i]=(a[i-1]+a[i])%k; ll cnt=0; rep(i,1,n){ cnt+=b[a[i]]++;//就是按顺序一一将相减后等于0的进行配对 } cout<<cnt+b[0]<<endl;//0可以独自忍受孤独 return 0; }
-