Submit | All submissions | Best solutions | Back to list |
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.
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 |
hide comments
2024-07-15 17:25:42
have any one have test that can fall my code ? <snip> [Simes]: this is not the place to debug code. Please use the forum. Last edit: 2024-07-15 22:34:01 |
|
2020-07-15 19:51:41
take care the range of value of s[i] |
|
2019-07-13 15:59:53
those who are getting WA!! try this one input 6 2 3 4 3 4 3 4 output 1 |
|
2018-07-05 09:25:49
use modulo operation wisely. |
|
2017-10-27 17:44:28
very easy cake walk! |
|
2016-08-08 17:45:43
why C++ 5 is not available on this problem. I got many compile error. Pls add it. |
|
2015-07-12 18:04:55 xxbloodysantaxx
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!! |
|
2015-06-04 05:07:20 Rang
Be mindful of modular Arithmetic :) . |
|
2014-12-10 19:58:34 Raghuram
what's the answer to 4 2 0 1 0 1 Are the two (0,1) pairs considered the same or different subsequences ? |
|
2012-06-14 06:08:41 mindfuck
similar problem INCSEQ |