| Submit | All submissions | Best solutions | Back to list |
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.
| Added by: | Neal Wu |
| Date: | 2008-06-20 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ERL JS-RHINO |
| Resource: |
hide comments
|
|||||||||
|
2016-02-25 20:07:09
what will be the output for 4,3 1,2,4,10 |
|||||||||
|
2016-01-25 04:21:31 minhthai
oh man the mod costs me too many WA :(( |
|||||||||
|
2015-12-30 18:09:20 GAURAV CHANDEL
Cool ... very cool problem.... |
|||||||||
|
2015-12-12 18:40:19 Ankit Sultana
Check the modulus, it's not 10^9+7 |
|||||||||
|
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 :) |
|||||||||
|
2015-10-25 14:36:25 Karun
If you have a complexity of ~ O(n*k*log(k*100000)) and you're still getting a TLE -> optimize modulus operations -> normalize the input array |
|||||||||
|
2015-09-26 02:36:28 Sliti khaled
Nice one :D |
|||||||||
|
2015-08-28 09:42:08 Ayur Jain
Nice problem involving DP+BIT :) |
|||||||||
|
2015-08-19 05:51:04 SangKuan
why the ans is 2.there only one increasing sequence 1 2 10 |
|||||||||
|
2015-07-12 13:07:49 xxbloodysantaxx
Such a big silly Mistake !! I was switching the loops ! without even thinking! Nice problem !! |
|||||||||
RSS