前缀和数组+数论中的组合思想优化

解题思路:

这是蓝桥杯2017年B组的最后一道编程题。 

首先此题想到前缀和的思想，用前缀和数组的两项相减得到字串之和，能通过33%的数据，差不多是N<=1000左右时能通过。

其次如果想要100%通过，还要用优化的方法：取模得到的数来用组合数运算（任选两个余数一样的相减一定能被K整除）。

通过以上的优化以后，我们就少了枚举的操作，从二维降到一维上，时间复杂度从O(n^2)降到O(n)。

注意事项:

注意输入的范围，如果K=1的时候，会有10e10 个数据，超出int范围，这也是为什么我结果报出运行错误的原因。

参考代码:

#include<bits/stdc++.h>

using namespace std;

#define MAX 100005

typedef long long int ll;

int N,K;

ll ans=0;

int A[MAX];

vector<ll> S;

ll rec[MAX];

void slove()

{

S.clear();

for(int j=0;j<N;j++){

if(j==0) S.push_back(A[0]);

else S.push_back((S[j-1]+A[j]));

}

rec[0]++;

for(vector<ll>::iterator it=S.begin();it!=S.end();it++) rec[*(it)%K]++;

}

int main()

{

cin>>N>>K;

for(int i=0;i<N;i++) cin>>A[i];

slove();

for(int i=0;i<K;i++) ans+=rec[i]*(rec[i]-1)/2;

cout<<ans;

return 0;

}