INCDSEQ - Distinct Increasing Subsequences
Given a sequence of N (1 ≤ N ≤ 10,000) integers S1, ..., SN (0 ≤ Si < 1,000,000,000), compute the number of distinct increasing subsequences of S with length K (1 ≤ K ≤ 50 and K ≤ N).
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 distinct increasing subsequences of S of length K, modulo 5,000,000.
Example
Input: 4 3 1 2 2 10 Output: 1
The only increasing subsequence of length 3 is 1, 2, 10.
hide comments
omarabdo10:
2024-07-15 17:25:42
have any one have test that can fall my code ?
|
|
pandey101299:
2020-07-15 19:51:41
take care the range of value of s[i] |
|
agrawal117:
2019-07-13 15:59:53
those who are getting WA!!
|
|
sherlock11:
2018-07-05 09:25:49
use modulo operation wisely. |
|
danish4200:
2017-10-27 17:44:28
very easy cake walk!
|
|
sieunhanbom04:
2016-08-08 17:45:43
why C++ 5 is not available on this problem. I got many compile error. Pls add it. |
|
xxbloodysantaxx:
2015-07-12 18:04:55
Wow I am a programmer and I make silly mistakes which irritate me a lot just because the compiler is too stupid to handle it!! |
|
Rang:
2015-06-04 05:07:20
Be mindful of modular Arithmetic :) . |
|
Raghuram:
2014-12-10 19:58:34
what's the answer to
|
|
mindfuck:
2012-06-14 06:08:41
similar problem INCSEQ |
Added by: | Bin Jin |
Date: | 2008-06-22 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: CPP |
Resource: | co-author: Neal Wu |