网站国外空间,济南软件公司排名,wordpress集群,j建设网站多多的求和计算 多多路上从左到右有N棵树#xff08;编号1#xff5e;N#xff09;#xff0c;其中第i个颗树有和谐值Ai。 多多鸡认为#xff0c;如果一段连续的树#xff0c;它们的和谐值之和可以被M整除#xff0c;那么这个区间整体看起来就是和谐的。 现在多多鸡想请…
多多的求和计算 多多路上从左到右有N棵树编号1N其中第i个颗树有和谐值Ai。 多多鸡认为如果一段连续的树它们的和谐值之和可以被M整除那么这个区间整体看起来就是和谐的。 现在多多鸡想请你帮忙计算一下满足和谐条件的区间的数量。 时间限制C/C 1秒其他语言2秒 空间限制C/C 256M其他语言512M 输入描述 第一行有2个整数N和M表示树的数量以及计算和谐值的参数。 1 N 100,000, 1 M 100 第二行有N个整数Ai, 分别表示第i个颗树的和谐值。 0 Ai 1,000,000,000 输出描述 共1行每行1个整数表示满足整体是和谐的区间的数量。 示例1 输入例子 5 2 1 2 3 4 5 输出例子 6 例子说明 长度为1: [2], [4] 长度为2: 无 长度为3: [1,2,3], [3,4,5] 长度为4: [1,2,3,4], [2,3,4,5] 长度为5: 无 共6个区间的和谐值之和可以被2整除。
题解
前缀和取模计数后面的前缀和减去前面的前缀和得到这个区间的和。
AC代码
#include bits/stdc.h
using namespace std;
typedef long long ll;
const int maxn 1e55;
int n,m;
int arr[maxn];
int sum[105];
int main()
{cinnm;for(int i0;in;i){cinarr[i];arr[i] % m;}memset(sum,0,sizeof(sum));sum[0] 1;int total 0;ll res 0;for(int i0;in;i){total arr[i];total % m;for(int j0;jm;j){if((totalm-j)%m0){res (ll)sum[j];}}sum[total] 1;}coutresendl;return 0;
}
