当前位置: 代码迷 >> 综合 >> 51nod 2522
  详细解决方案

51nod 2522

热度:67   发布时间:2024-01-15 06:40:07.0

小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;
}