INCSEQ - Increasing Subsequences
Given a sequence of N (1 ≤ N ≤ 10,000) integers S1, ..., SN (0 ≤ Si < 100,000), compute the number of increasing subsequences of S with length K (1 ≤ K ≤ 50 and K ≤ N); that is, the number of K-tuples i1, ..., iK such that 1 ≤ i1 < ... < iK ≤ N and Si1 < ... < SiK.
Input
The first line contains the two integers N and K. The following N lines contain the integers of the sequence in order.
Output
Print a single integer representing the number of increasing subsequences of S of length K, modulo 5,000,000.
Example
Input: 4 3 1 2 2 10 Output: 2
The two 3-tuples are (1, 2, 4) and (1, 3, 4), both corresponding to the subsequence 1, 2, 10.
hide comments
|
raj_394:
2015-11-13 05:51:05
Nice problem for understanding Binary Index Trees. Advice is to understand BIT properly before doing this one.. go through this link for getting familiar to BIT https://www.hackerearth.com/notes/binary-indexed-tree-made-easy-2/ .... happy coding :) |
|
Karun :
2015-10-25 14:36:25
If you have a complexity of ~ O(n*k*log(k*100000)) and you're still getting a TLE
|
|
Sliti khaled:
2015-09-26 02:36:28
Nice one :D |
|
Ayur Jain:
2015-08-28 09:42:08
Nice problem involving DP+BIT :) |
|
SangKuan:
2015-08-19 05:51:04
why the ans is 2.there only one increasing sequence 1 2 10 |
|
xxbloodysantaxx:
2015-07-12 13:07:49
Such a big silly Mistake !! I was switching the loops ! without even thinking! Nice problem !! |
|
Pagan Min:
2015-06-24 14:22:47
bit + normalisation
|
|
Ahmad Musa:
2015-05-19 10:09:48
I get WA on 10 th case . https://ideone.com/doQLl9
|
|
Sunil:
2015-04-18 13:08:32
Trying to do multiple cases as in tutorial problem eldorado costed a lot TLE :( |
|
arp_ee:
2015-03-30 17:18:26
nice problem !! learnt a lot !! |
Added by: | Neal Wu |
Date: | 2008-06-20 |
Time limit: | 0.143s-0.286s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO |
Resource: |