問題一覧 > 通常問題

No.1505 Zero-Product Ranges

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 244
作問者 : oliverx3oliverx3 / テスター : kichi2004_kichi2004_ 遭難者遭難者 yuto1115yuto1115
3 ProblemId : 6129 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-14 11:30:21

問題文

$0$ または $1$ からなる長さ $N$ の数列 $A$ が与えられます。数列の $i\ (1\leq i \leq N)$ 番目の要素は $A_i$ です。

$\displaystyle \prod_{i=l}^{r}A_i = 0$ である $(l,\ r)\ (1 \leq l \leq r \leq N)$ の組は何通りあるか求めなさい。

ただし、
$\displaystyle \prod_{i=l}^{r}A_i\ =\ A_l \times A_{l+1} \times \cdots \times A_{r}$
です。

制約

  • $1 \leq N \leq 2 \times 10^5$
  • $A_i = 0,\ 1\ (1 \leq i \leq N)$
  • 入力は全て整数である

入力

$N$
$A_1\ A_2\ \cdots \ A_N$

出力

答えを出力し、末尾で改行してください。

サンプル

サンプル1
入力
3
1 0 1
出力
4

題意を満たす組は $(l,\ r) = (1,\ 2),\ (1,\ 3),\ (2,\ 2),\ (2,\ 3)$ の $4$ 通りです。

サンプル2
入力
5
1 1 1 1 1
出力
0

題意を満たす組が存在しないこともあります。

サンプル3
入力
10
1 1 0 1 1 1 0 0 1 1
出力
43

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。