3734 - Count Odd Increasing Subsequences 3734 - Contando Subsecuencias Crecientes Impares 3734 - Count Odd Increasing Subsequences

Statistics Sub: 251 | AC: 106 | AC%: 42,23 | Score: 1,64
Created by Carlos Joa Fong
Added by cjoa (2016-09-10)
Limits
Total Time: 10000 MS | Test Time: 2000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Given a sequence of N integers A1, A2, ..., AN, count the number of strictly increasing subsequences whose sum is odd.

A subsequence of sequence A is obtained by selecting some positions of the sequence A, keeping the elements at those positions in the same order, and removing all elements at positions that were not selected. A strictly increasing subsequence is a subsequence where the elements at the selected indices are increasing. Two subsequences are different if there is a position selected in one subsequence but not the other.

More formally, a sequence S1, ..., Sk is called a strictly increasing subsequence of sequence A1, ..., AN, if there is a sequence of indices 1  ≤  i1  <  ...  <  ik ≤  N such that S1  =  Ai1, ..., Sk  =  Aik and S1 < S2 < ... < Sk. A subsequence S is different than subsequence T if there exists an index  that is selected by S but not by T.

;jsessionid=998967D9D977AB618E36193AE7E2FF53
Dada una secuencia de N números enteros A1, A2, ..., AN, determina la cantidad de subsecuencias (estrictamente) crecientes cuya suma es impar.

Una subsecuencia de la secuencia A se obtiene eligiendo algunas de las posiciones de la secuencia A, manteniendo los elementos en dichas posiciones en el mismo orden original y eliminando todos los demas elementos en posiciones que no fueron seleccionados. Una subsecuencia es estrictamente creciente si sus elementos en las posiciones seleccionadas crecen de menor a mayor. Dos subsecuencias se consideran diferentes si existe una posición elegida en una subsecuencia pero no en la otra.

De manera más formal, una secuencia S1, ..., Sk es una subsecuencia estrictamente creciente de la secuencia A1, ..., AN, si existe una secuencia de índices 1  ≤  i1  <  ...  <  ik ≤  N que satisface las condiciones S1  =  Ai1, ..., Sk  =  Aik y S1 < S2 < ... < Sk. Una subsecuencia S is diferente a la subsecuencia T si existe un índice el cual es seleccionado por S, pero no por T.

Given a sequence of N integers A1, A2, ..., AN, count the number of strictly increasing subsequences whose sum is odd.

A subsequence of sequence A is obtained by selecting some positions of the sequence A, keeping the elements at those positions in the same order, and removing all elements at positions that were not selected. A strictly increasing subsequence is a subsequence where the elements at the selected indices are increasing. Two subsequences are different if there is a position selected in one subsequence but not the other.

More formally, a sequence S1, ..., Sk is called a strictly increasing subsequence of sequence A1, ..., AN, if there is a sequence of indices 1  ≤  i1  <  ...  <  ik ≤  N such that S1  =  Ai1, ..., Sk  =  Aik and S1 < S2 < ... < Sk. A subsequence S is different than subsequence T if there exists an index  that is selected by S but not by T.

;jsessionid=998967D9D977AB618E36193AE7E2FF53

Input specification

In the first line of input, we have a single integer C (1 ≤ C ≤ 100), which corresponds to the number of test cases to process.

Each test case consists of two lines:

  1. Line 1 of each test case contains a single integer N (1 ≤ N ≤ 105), the length of the sequence A.
  2. Line 2 contains a sequence of N space separated integers Ai (0 ≤ Ai ≤ 109 for 1 ≤ i ≤ N).

The sum of all N over all test cases does not exceed 2 * 105.

En la primera línea de entrada, tenemos un solo número entero C (1 ≤ C ≤ 100), el cual corresponde a la cantidad de casos de pruebas a procesar.

Cada caso de prueba consiste en dos líneas:

  1. Línea 1 contiene un solo número entero N (1 ≤ N ≤ 105), la longitud de la secuencia A.
  2. Línea 2 contiene la secuencia de N números enteros Ai (0 ≤ Ai ≤ 109 para 1 ≤ i ≤ N).

La suma total de las N sobre todos los casos de pruebas no excede 2 * 105.

In the first line of input, we have a single integer C (1 ≤ C ≤ 100), which corresponds to the number of test cases to process.

Each test case consists of two lines:

  1. Line 1 of each test case contains a single integer N (1 ≤ N ≤ 105), the length of the sequence A.
  2. Line 2 contains a sequence of N space separated integers Ai (0 ≤ Ai ≤ 109 for 1 ≤ i ≤ N).

The sum of all N over all test cases does not exceed 2 * 105.

Output specification

For each test case, in the order given in the input, count the number of strictly increasing subsequences whose sum is odd. As this number may be too large, print out its remainder after dividing it by 109 + 7.
;jsessionid=998967D9D977AB618E36193AE7E2FF53
Por cada caso de prueba, en el orden dado por la entrada, calcula la cantidad de subsecuencias estrictamente crecientes cuya suma es impar. En vez de imprimir el número, el cual puede ser enorme, imprime su remanente de dividirlo por 109 + 7.
In the first line of input, we have a single integer C (1 ≤ C ≤ 100), which corresponds to the number of test cases to process.

Each test case consists of two lines:

  1. Line 1 of each test case contains a single integer N (1 ≤ N ≤ 105), the length of the sequence A.
  2. Line 2 contains a sequence of N space separated integers Ai (0 ≤ Ai ≤ 109 for 1 ≤ i ≤ N).

The sum of all N over all test cases does not exceed 2 * 105.

Sample input

2
3
1 2 2
5
5 1 4 3 5

Sample output

3
7

Hint(s)

In the first sample test case, the 3 subsequences are: (1), (1, 2), (1, 2)
In the second sample test case, the 7 subsequences are: (5), (1), (1, 4), (1, 3, 5), (4, 5), (3), (5)
En el primer ejemplo, las 3 subsecuencias crecientes son: (1), (1, 2), (1, 2)
En el segundo ejemplo, las 7 subsecuencias son: (5), (1), (1, 4), (1, 3, 5), (4, 5), (3), (5)
In the first sample test case, the 3 subsequences are: (1), (1, 2), (1, 2)
In the second sample test case, the 7 subsequences are: (5), (1), (1, 4), (1, 3, 5), (4, 5), (3), (5)

Recommendation

We have carefully selected several similar problems: 3379 | 3378 | 3573 | 3599 | 3954 | 3147