305220: CF992D. Nastya and a Game

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Nastya and a Game

题意翻译

## 题目描述 $Nastya$ 在生日那天收到了一个大小为 $n$ 的数组,她想知道数组存放的序列中,有多少的子串满足其中所有的数的乘积是数的总和的 $k$ 倍。请帮她得到答案。 ## 输入格式 第 $1$ 行,有 $2$ 个整数,分别表示数组的大小 $n$ 和倍数 $k$ 。 (数据范围: $1 \leqslant n \leqslant 2 \times 10^{5}$ , $1 \leqslant k \leqslant 10^5$ ) 第 $2$ 行,有 $n$ 个整数,表示数组的元素 $a_i$ 。 (数据范围: $1 \leqslant a_i \leqslant 10^8$ ) ##输出格式 仅 $1$ 个整数,表示符合条件的子串数量。 ##提示与说明 - 第 $1$ 组样例的解释: 只有 $1$ 子串 $\{1\}$ ,因为 $\frac{1}{1}=k=1$ ,所以它恰好是符合条件的。 - 第 $2$ 组样例的解释: $\{6,\ 3\}$ 中所有数的乘积是 $18$ ,总和是 $9$ ,因为 $\frac{18}{9}=k=2$ ,所以它符合条件。 $\{3,\ 8,\ 1\}$ 中所有数的乘积是 $24$ ,总和是 $12$ ,因为 $\frac{24}{12} = k = 2$ ,所以它也符合条件。 综上所述,共有 $2$ 个子串符合条件。 感谢@Sooke 提供翻译以及@ZqlwMatt 修正

题目描述

Nastya received one more array on her birthday, this array can be used to play a traditional Byteland game on it. However, to play the game the players should first select such a subsegment of the array that ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF992D/d4ce700b04162c79acfb0ca90e215f2e76a7e459.png), where $ p $ is the product of all integers on the given array, $ s $ is their sum, and $ k $ is a given constant for all subsegments. Nastya wonders how many subsegments of the array fit the described conditions. A subsegment of an array is several consecutive integers of the array.

输入输出格式

输入格式


The first line contains two integers $ n $ and $ k $ ( $ 1<=n<=2·10^{5} $ , $ 1<=k<=10^{5} $ ), where $ n $ is the length of the array and $ k $ is the constant described above. The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{8} $ ) — the elements of the array.

输出格式


In the only line print the number of subsegments such that the ratio between the product and the sum on them is equal to $ k $ .

输入输出样例

输入样例 #1

1 1
1

输出样例 #1

1

输入样例 #2

4 2
6 3 8 1

输出样例 #2

2

说明

In the first example the only subsegment is $ [1] $ . The sum equals $ 1 $ , the product equals $ 1 $ , so it suits us because ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF992D/d76ba10e5aa32f7bf5739774163d1420597c494b.png). There are two suitable subsegments in the second example — $ [6,3] $ and $ [3,8,1] $ . Subsegment $ [6,3] $ has sum $ 9 $ and product $ 18 $ , so it suits us because ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF992D/8e7401c7355d4401ff07e132e35f5974029bbcef.png). Subsegment $ [3,8,1] $ has sum $ 12 $ and product $ 24 $ , so it suits us because ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF992D/ef0bb2f1755f7a6074cc541c8ecaec98cbaaeaf9.png).

Input

题意翻译

## 题目描述 $Nastya$ 在生日那天收到了一个大小为 $n$ 的数组,她想知道数组存放的序列中,有多少的子串满足其中所有的数的乘积是数的总和的 $k$ 倍。请帮她得到答案。 ## 输入格式 第 $1$ 行,有 $2$ 个整数,分别表示数组的大小 $n$ 和倍数 $k$ 。 (数据范围: $1 \leqslant n \leqslant 2 \times 10^{5}$ , $1 \leqslant k \leqslant 10^5$ ) 第 $2$ 行,有 $n$ 个整数,表示数组的元素 $a_i$ 。 (数据范围: $1 \leqslant a_i \leqslant 10^8$ ) ##输出格式 仅 $1$ 个整数,表示符合条件的子串数量。 ##提示与说明 - 第 $1$ 组样例的解释: 只有 $1$ 子串 $\{1\}$ ,因为 $\frac{1}{1}=k=1$ ,所以它恰好是符合条件的。 - 第 $2$ 组样例的解释: $\{6,\ 3\}$ 中所有数的乘积是 $18$ ,总和是 $9$ ,因为 $\frac{18}{9}=k=2$ ,所以它符合条件。 $\{3,\ 8,\ 1\}$ 中所有数的乘积是 $24$ ,总和是 $12$ ,因为 $\frac{24}{12} = k = 2$ ,所以它也符合条件。 综上所述,共有 $2$ 个子串符合条件。 感谢@Sooke 提供翻译以及@ZqlwMatt 修正

加入题单

上一题 下一题 算法标签: