【分糖果】

news/2024/10/30 11:32:46/

N N N 个盒子排成一排,第 i i i 个盒子里有 A i A_i Ai 个糖果。你需要从一些连续的盒子里取出糖果,分给 M M M 个小朋友,使得每个小朋友得到的糖果数量相等。求有多少种取法满足以下两个条件:

  • 取出的盒子数为 r − l + 1 r-l+1 rl+1,其中 1 ≤ l ≤ r ≤ N 1\le l\le r\le N 1lrN
  • 分给每个小朋友的糖果数量是 K K K 的倍数,其中 K = ∑ i = l r A i M K=\frac{\sum_{i=l}^r A_i}{M} K=Mi=lrAi

输入格式

第一行包含两个整数 N N N M M M

第二行包含 N N N 个整数 A 1 , A 2 , … , A N A_1,A_2,\dots,A_N A1,A2,,AN

输出格式

输出一个整数,表示满足条件的取法数。

数据范围

  • 1 ≤ N ≤ 1 0 5 1\le N\le 10^5 1N105
  • 1 ≤ M ≤ 10 1\le M\le 10 1M10
  • 1 ≤ A i ≤ 1 0 9 1\le A_i\le 10^9 1Ai109

输入样例1:

3 2
4 1 5

输出样例1:

3

输入样例2:

13 17
29 7 5 7 9 51 7 13 8 55 42 9 81

输出样例2:

6

输入样例3:

10 400000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

输出样例3:

25

提示

样例1解释:

符合条件的取法有 ( 1 , 3 ) , ( 2 , 3 ) , ( 3 , 3 ) (1,3),(2,3),(3,3) (1,3),(2,3),(3,3)

样例2解释:

符合条件的取法有 ( 1 , 2 ) , ( 2 , 3 ) , ( 3 , 4 ) , ( 4 , 5 ) , ( 5 , 6 ) , ( 6 , 7 ) (1,2),(2,3),(3,4),(4,5),(5,6),(6,7) (1,2),(2,3),(3,4),(4,5),(5,6),(6,7)

样例3解释:

符合条件的取法有 ( 1 , 1 ) , ( 1 , 2 ) , ( 1 , 3 ) , ( 1 , 4 ) , ( 1 , 5 ) , ( 1 , 6 ) , ( 1 , 7 ) , ( 1 , 8 ) , ( 1 , 9 ) , ( 1 , 10 ) , ( 2 , 2 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 2 , 5 ) , ( 2 , 6 ) , ( 2 , 7 ) , ( 2 , 8 ) , ( 2 , 9 ) , ( 2 , 10 ) , ( 3 , 3 ) , ( 3 , 4 ) , ( 3 , 5 ) , ( 3 , 6 ) , ( 3 , 7 ) (1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(1,10),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(2,10),(3,3),(3,4),(3,5),(3,6),(3,7) (1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(1,10),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(2,10),(3,3),(3,4),(3,5),(3,6),(3,7)


http://www.ppmy.cn/news/98768.html

相关文章

C++11 -- lambda表达式

文章目录 lamaba表达式的引入lambda表达式语法lamabda达式各部分说明捕获列表说明 lamaba表达式底层原理探索 lamaba表达式的引入 在C11之前,如果我们想对自定义类型Goods排序,可以根据姓名,价格,学号按照从大到小或者从小到大的方式排序,可是,这样我们要写额外写6个相关的仿函…

springboot配置Swagger3.0

springboot配置Swagger3.0 1、pom加入依赖 我们创建一个SpringBoot项目&#xff0c;引入 swagger3 依赖 <dependency><groupId>io.springfox</groupId><artifactId>springfox-boot-starter</artifactId><version>3.0.0</version>…

电脑msvcp120.dll缺失怎么办?由于找不到msvcp120.dll的解决方案

MSVCP120.dll文件是Windows操作系统中的一种动态链接库文件。它是由Microsoft C软件包提供的重要组件。当系统提示“MSVCP120.dll文件缺失”时&#xff0c;可能会导致某些应用程序无法正常运行。 以下是修复MSVCP120.dll缺失问题的几种方法&#xff1a; 方法一&#xff1a;修复…

一台服务器通过nginx安装多个web应用

1.首先安装nginx网站服务器 yum install nginx 2.nginx 的主配置文件&#xff1a;/etc/nginx/nginx.conf (一台服务器有两个域名部署) 我们在/etc/nginx/nginx.d/下创建一个conf文件&#xff0c;这个文件会被嵌套到主配置文件当中 server { listen 80; …

VS2022发布独立部署的.net程序

.net core支持依赖框架部署和独立部署两种方式&#xff0c;之前学习时是在VSCode中使用dotnet命令发布的。但是在VS2022中却不知道该如何设置。以获取PDF文件使用字体的项目为例&#xff0c;VS2022中默认编译的是依赖框架部署方式&#xff08;编译的结果如下图所示&#xff09;…

动态规划2:题目

目录 第1题 Fibonacci 第2题 字符串分割(Word Break) .第3题 三角矩阵(Triangle) 第4题 路径总数(Unique Paths) 第5题 最小路径和(Minimum Path Sum) 第6题 背包问题 第7题 回文串分割(Palindrome Partitioning) 第8题 编辑距离(Edit Distance) 第9题 不同子序列(Dist…

【面试集锦 - 嵌入式软件工程师 - MCU篇】

MCU / 单片机 常用芯片 一般会问一下使用的芯片是什么&#xff0c;并对其做一些介绍。 嵌入式系统常用的微控制器单元&#xff08;MCU&#xff09;是一种集成了处理器核心、存储器、输入/输出接口和其他外设功能的芯片。它们被广泛应用于各种嵌入式系统&#xff0c;如家电、汽…

CVPR2023(论文笔记)

Boosting Verified Training for Robust Image Classifications via Abstraction 基于抽象的鲁棒图像分类模型高效训练与验证方法&#xff1a; 针对问题&#xff1a; 深度神经网络在面对对抗性攻击时的鲁棒性问题 提出了一种基于抽象的、经过认证的训练方法&#xff0c;用于…