Petya and Sequence
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Little Petya likes integer numbers a lot. Recently he has received a sequence of integers as a gift from his mother. Petya calls a sequence of N integers Ai beautiful if there exist a sequence of N integer numbers Bi for which the following conditions hold:
- At least one number Bi differs from 0.
- For every j from 0 to N-1 the following holds:
A0* Bj + A1* B(j + 1) mod N + ... + AN-1* B(j + N - 1) mod N = 0.
Please, help Petya to check if his sequence Ai is beautiful.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of elements in Petya's sequence. The second line contains N space-separated integers A0, A1, ..., AN-1 denoting the sequence.
For each test case, output a single line containing the word "YES"(without quotes) if Petya's sequence is beautiful and "NO", otherwise.
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 3 * 104
- -1000 ≤ Ai ≤ 1000
Sum of N for all test cases in a single input file will not exceed 150 000.
Input: 4 3 1 0 0 3 1 1 1 4 2 -4 1 1 5 1 3 2 1 5 Output: NO YES YES NO
Example case 2. One of the possible sequences B is (1, -1, 0).
Example case 3. One of the possible sequences B is (1, 1, 1, 1).
|Tags||KADR, dec13, fft, hard, maths|
|Time Limit:||8 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.