問題一覧 > 通常問題

No.2956 Substitute with Average

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 43
作問者 : 👑 binap / テスター : startcpp hamamu
5 ProblemId : 11424 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-11-02 20:01:39

問題文

NN 項の整数列 (A1,⋯ ,AN)(A_1,\cdots, A_N) が与えられる。次の操作を 11 回行うことで得られる数列は何通りあるかを求めてください。

・ 1≤L≤R≤N1\leq L \leq R \leq N なる整数組 (L,R)(L, R) を選ぶ。 AL,AL+1,⋯ ,ARA_L, A_{L + 1}, \cdots, A_R をそれらの平均で置き換える。つまり i=L,L+1,…,Ri = L, L + 1, \dots, R について同時に AiA_i を AL+⋯+ARR−L+1\dfrac{A_L + \cdots + A_R}{R - L + 1} で置き換える。

制約

・ 1≤N≤1051\leq N \leq 10^5

・ 1≤Ai≤301\leq A_i \leq 30 (1≤i≤N)(1\leq i \leq N)

・入力は全て整数

入力

NN
A1A_1 A2A_2 ⋯\cdots ANA_N

出力

得られる数列は何通りあるかを求めて 11 行に出力してください。

サンプル

サンプル1
入力
3
2 4 6
出力
4

操作によって 44 通りの数列が得られます。得られる数列と得るための具体的な方法を挙げます。

・(2,4,6)(2, 4, 6) は (L,R)=(1,1)(L, R) = (1, 1) として操作することにより得られます。

・(3,3,6)(3, 3, 6) は (L,R)=(1,2)(L, R) = (1, 2) として操作することにより得られます。

・(2,5,5)(2, 5, 5) は (L,R)=(2,3)(L, R) = (2, 3) として操作することにより得られます。

・(4,4,4)(4, 4, 4) は (L,R)=(1,3)(L, R) = (1, 3) として操作することにより得られます。

各数列を得る方法は必ずしも一意には定まりません。

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

サンプル3
入力
2
1 2
出力
2

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