Dotcpp  >  编程题库  >  蓝桥杯2021年第十二届国赛真题-和与乘积
题目 2622:

蓝桥杯2021年第十二届国赛真题-和与乘积

时间限制: 1s 内存限制: 128MB 提交: 1330 解决: 185

题目描述

给定一个数列 A = (a1, a2, · · · , an),问有多少个区间 [L, R] 满足区间内元素的乘积等于他们的和,即 aL · aL+1 · · · aR = aL + aL+1 + · · · + aR 。

输入格式

输入第一行包含一个整数 n,表示数列的长度。
第二行包含 n 个整数,依次表示数列中的数 a1, a2, · · · , an。

输出格式

输出仅一行,包含一个整数表示满足如上条件的区间的个数。

样例输入

4
1 3 2 2

样例输出

6

提示

【样例解释】
符合条件的区间为 [1, 1], [1, 3], [2, 2], [3, 3], [3, 4], [4, 4]。
【评测用例规模与约定】
对于 20% 的评测用例,n ≤ 3000;
对于 50% 的评测用例,n ≤ 20000;
对于所有评测用例,1 ≤ n ≤ 200000, 1 ≤ ai ≤ 200000。
标签