問題一覧 > 通常問題

No.2956 Substitute with Average

レベル : / AI推定難易度 : 1950 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 47
作問者 : 👑 binap / テスター : startcpp 👑 hamamu
お気に入りにしたユーザー ProblemId : 11424 / 自分の提出
問題文最終更新日: 2024-11-02 20:01:39
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 452 (順位表) の他の問題:

Problem Statement

You are given an integer sequence $(A_1,\cdots, A_N)$ with $N$ terms. Find the number of distinct sequences that can be obtained by performing the following operation $1$ time.

・ Choose a pair of integers $(L, R)$ such that $1\leq L \leq R \leq N$. Replace $A_L, A_{L + 1}, \cdots, A_R$ with their average. That is, for $i = L, L + 1, \dots, R$, simultaneously replace $A_i$ with $\dfrac{A_L + \cdots + A_R}{R - L + 1}$.

Constraints

・ $1\leq N \leq 10^5$

・ $1\leq A_i \leq 30$ $(1\leq i \leq N)$

・All input values are integers.

Input

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

Output

Find the number of sequences that can be obtained and print it on $1$ line.

Sample

Sample 1
Input
3
2 4 6
Output
4

$4$ different sequences can be obtained by the operation. The obtainable sequences and specific ways to obtain them are listed below.

・$(2, 4, 6)$ is obtained by performing the operation with $(L, R) = (1, 1)$.

・$(3, 3, 6)$ is obtained by performing the operation with $(L, R) = (1, 2)$.

・$(2, 5, 5)$ is obtained by performing the operation with $(L, R) = (2, 3)$.

・$(4, 4, 4)$ is obtained by performing the operation with $(L, R) = (1, 3)$.

The way to obtain each sequence is not necessarily unique.

Sample 2
Input
4
5 5 5 5
Output
1

Sample 3
Input
2
1 2
Output
2

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