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
|
ghost_wire:
2016-02-25 20:07:09
what will be the output for 4,3
|
|
minhthai:
2016-01-25 04:21:31
oh man the mod costs me too many WA :(( |
|
GAURAV CHANDEL:
2015-12-30 18:09:20
Cool ... very cool problem.... |
|
Ankit Sultana:
2015-12-12 18:40:19
Check the modulus, it's not 10^9+7 |
|
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 !! |
| 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: |
RSS