No.2956 Substitute with Average
タグ : / 解いたユーザー数 35
作問者 : 👑
binap
/ テスター :
startcpp
hamamu
問題文
$N$ 項の整数列 $(A_1,\cdots, A_N)$ が与えられる。次の操作を $1$ 回行うことで得られる数列は何通りあるかを求めてください。
・ $1\leq L \leq R \leq N$ なる整数組 $(L, R)$ を選ぶ。 $A_L, A_{L + 1}, \cdots, A_R$ をそれらの平均で置き換える。つまり $i = L, L + 1, \dots, R$ について同時に $A_i$ を $\dfrac{A_L + \cdots + A_R}{R - L + 1}$ で置き換える。
制約
・ $1\leq N \leq 10^5$
・ $1\leq A_i \leq 30$ $(1\leq i \leq N)$
・入力は全て整数
入力
$N$ $A_1$ $A_2$ $\cdots$ $A_N$
出力
得られる数列は何通りあるかを求めて $1$ 行に出力してください。
サンプル
サンプル1
入力
3 2 4 6
出力
4
操作によって $4$ 通りの数列が得られます。得られる数列と得るための具体的な方法を挙げます。
・$(2, 4, 6)$ は $(L, R) = (1, 1)$ として操作することにより得られます。
・$(3, 3, 6)$ は $(L, R) = (1, 2)$ として操作することにより得られます。
・$(2, 5, 5)$ は $(L, R) = (2, 3)$ として操作することにより得られます。
・$(4, 4, 4)$ は $(L, R) = (1, 3)$ として操作することにより得られます。
各数列を得る方法は必ずしも一意には定まりません。
サンプル2
入力
4 5 5 5 5
出力
1
サンプル3
入力
2 1 2
出力
2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。