Maxim and Progressions
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Maxim likes arithmetic progressions and does not like sequences which are not arithmetic progressions.Now he is interested in the question: how many subsequences of his sequence a, consisting of n elements, are not arithmetic progressions. Sequence s, s, ..., s[k] is called a subsequence of sequence a, a, ..., a[n], if there will be such increasing sequence of indices i, i, ..., i[k] (1 ≤ i < i < ... < i[k] ≤ n), that a[i[j]] = s[j]. In other words, sequence s can be obtained from the a by deleting some elements. Sequence s, s, ..., s[k] is called an arithmetic progression, if it can be represented as :
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 an integer n — the number of elements in the sequence. The next line of the test case contains n integer, a, a, ..., a[n] — elements of the sequence.
For each test case print the remainder of the division the answer on 1000000007 (10^9 + 7). All answers print on different lines.
1 ≤ T ≤ 10
1 ≤ n ≤ 200000
1 ≤ a[i] ≤ 100
Input: 2 1 1 3 1 2 1 Output: 0 1
|Tags||combinatorics, dynamic-programming, easy, june14, sereja|
|Time Limit:||2 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.