题目

小b喜欢和为K的倍数的序列。

现在有一个长度为n的序列A，请问A有多少个非空连续子序列是小b喜欢的。

输入

第一行输入一个正整数n；

第二行输入n个整数，表示A[i]，以空格隔开；

第三行输入一个正整数K；

其中1≤n≤30000，对于任意A[i]有-10000≤A[i]≤10000，2≤K≤10000

输出

输出一个数，表示子序列的数目

输入样例

6

4 5 0 -2 -3 1

5

输出样例

7

思路：实质要求有多少个连续区间和是 k 的倍数

考虑维护一个前缀和，由于数据范围问题，在求前缀和的过程中直接对 sum[i] 取模 k，由于求的是多少个连续区间和是 k 的倍数的个数，因此并不影响最终答案

在求出前缀和后，首先枚举终点，然后枚举长度，进行判断即可

源程序

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 40000+5;
const int dx[] = {0,0,-1,1,-1,-1,1,1};
const int dy[] = {-1,1,0,0,-1,1,-1,1};
using namespace std;

int a[N];
int sum[N];
int main() {
    int n,k;
    scanf("%d",&n);
    for(int i=1; i<=n; i++){
        scanf("%d",&a[i]);
//        sum[i]=a[i]+sum[i-1];
    }
    scanf("%d",&k);
    for(int i=1;i<=n;i++)
        sum[i]=(a[i]+sum[i-1])%k;

    int cnt=0;
    for(int i=1; i<=n; i++)//枚举终点
        for(int j=1;j<=i;j++)//枚举长度
            if((sum[i]-sum[j-1])%k==0)
                cnt++;
    printf("%d\n",cnt);
    return 0;
}