P8649 [蓝桥杯 2017 省 B] k 倍区间--前缀和--同余定理【蓝桥杯简单题-必开long long】

题目

分析

首先，看到”连续子序列求和”这一要求时，我们果断选择前缀和解答。

接着就要用到一个非常巧妙的“同余定理”——如果 sum[j] % K == sum[i] % K，这意味着 sum[j] - sum[i] 是 K 的倍数

（其实不难理解，就是2个都有多的一步分，将2个相减，刚好让其差%k=0，满足题目条件0）

其中运用最巧妙的是ans += y[sum[i] % k]++;【注意++的运算优先级，这个++是为下一次r准备的
太牛逼了！】 运用哈希表的方法存储余数出现的次数，
例如：出现第一个余数3时，ans+=0，y[3]=1;
出现第二个余数3时，ans+=1，y[3]=2；【y的每一次自加都是为下一次做准备】
出现第三个余数3时，ans+=2，y[3]=3；
（出现n个数的余数相等时，他们的区间个数为n-1个）

sum[]数组明明是从1开始存储的，为什么循环要从0开始？
因为题中说到区间[i,j]（i<=j），所以若数值本身是k的倍数也应被统计
例：k=3,数组[3,0,3]，但若从1开始，第一个3是不会被计入的
模拟：
i=0 ans+=0；y[0]=1；
i=1 ans+=1；y[1]=2；
i=2 ans+=2；y[2]=3；
i=3 ans+=3；y[3]=4；

综上可知，若i从1开始遍历，会少加一个自身能被K整除的情况

代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <queue>

#include <cctype>
using namespace std;
long long ans;
int n, k;
long long sum[100010], y[100010];
int main() {

	cin >> n >> k;

	for (int i = 1; i <= n; i++) {
		cin >> sum[i];
		sum[i] += sum[i - 1];
	}

	for (int i = 0; i <= n; i++) {
		ans += y[sum[i] % k]++;
	}
	cout << ans << endl;
	return 0;
}

还有一件事【老爹音】

这种代码比较少的题目，【说简单吧，有点难想到】，蓝桥杯这个老Y逼啊，测试的数据都得开到long long 才能通过【不开long long 见祖宗】