小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即可。不然会超时。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <list>
#include <vector>
using namespace std;
typedef long long ll;
const int N=100005;int sum[30005];
int a[30005];
int main()
{int n,k,tem,cnt=0;scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%d",&a[i]);scanf("%d",&k);for(int i=1;i<=n;++i)sum[i]=(sum[i-1]+a[i])%k;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;
}