P9509 『STA - R3』Aulvwc

Statistics is an old and fascinating subject. It is said that many years ago, a god named Huipu came to Earth and discovered humans, another intelligent species. **Hack testdata has been added in Subtask 5 and is not scored.**

A sequence $\{a_n\}$ is defined to be partition-averagable if and only if there exists a partition $S_1,S_2,\cdots,S_k$ of $\{1,2,\cdots,n\}$ (where $k>1$) such that for every integer $1\le i\le k$, the average of the elements in sequence $\{a\}$ whose indices are in $S_i$ are all the same **integer**. Now, given the sequence $\{a_n\}$, determine whether it is partition-averagable. If some definitions are not very clear to you, you can refer to the “Hint” section at the end.

The first line contains a positive integer $q$, which represents the number of queries. For each query, the first line contains a positive integer $n$, describing the length of the sequence. The second line contains $n$ integers, representing the sequence $\{a_n\}$.

Output $q$ lines. For each query, if the sequence is partition-averagable, output `Yes`; otherwise, output `No`.

### Hint A partition of a set $S$ is defined as a collection of sets $U_1,U_2,\cdots,U_k$, satisfying: - For all $i\neq j$, $U_i\cap U_j=\varnothing$. - $U_1\cup U_2\cup\cdots\cup U_k=S$. The average of a sequence $\{x_n\}$ is defined as: $$\bar x=\dfrac{x_1+x_2+\cdots+x_n}{n}=\dfrac 1n\sum_{i=1}^nx_i$$ ### Sample Explanation One possible partition for the first group of testdata: $\{1\},\{2\},\{3\},\{4\},\{5\}$. One possible partition for the second group of testdata: $\{1,5\},\{2,4\},\{3\}$. Note: the sets provided in a partition are sets of indices. ### Constraints **This problem uses bundled testdata and subtask dependencies.** $$ \newcommand{\arraystretch}{1.5} \begin{array}{c|c|c|c|c}\hline\hline \textbf{Subtask} & \bm{n}\le & \textbf{Score} & \textbf{Special Property}&\textbf{Dependent Subtasks}\\\hline \textsf{1} & 10 & 5 & \\\hline \textsf{2} & 10^3 & 20 & \sum a_i=0 \\\hline \textsf{3} & 100 & 25 & & \sf1\\\hline \textsf{4} & 10^3 & 50 & & \sf1\texttt{,}\ 3\\\hline \end{array} $$ For all testdata, $1\le q\le 10$, $2\le n\le 10^3$, $|a_i|\le 5\times10^3$. Translated by ChatGPT 5