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
|
abhi_8:
2023-08-28 07:46:17
SEGMENT Tree is like Sigma whereas BIT is like Beta, visualisation is very simple for Segment Tree. Use 50 STs. Last edit: 2023-08-28 07:46:59 |
|
Rishabh Agrawal:
2020-07-16 11:08:22
Can also be done in O(n*k*logn) using mergesort like technique |
|
yaseenmollik:
2020-03-22 19:05:58
Finally solved it using DP + 2D-BIT |
|
scolar_fuad:
2020-02-27 11:38:55
keep consider that someties BIT can't return value of index 0
|
|
ankkt16:
2019-10-13 08:35:47
if u r getting WA on test 10 make sure u hv taken care of 0's int the input |
|
abhinav_jain02:
2019-06-14 07:51:18
Note that array S can have zero. Last edit: 2019-06-14 07:52:48 |
|
gabrijel:
2019-03-30 21:56:34
go in 1 AC! |
|
fabijanb:
2019-03-27 21:52:48
solved it using bitset optimization, no wonder I won gold at IOI 2019 |
|
linkret:
2019-03-27 16:13:50
i wholeheadedly reccomend this task! |
|
joueur:
2019-01-21 16:41:11
DP+BIT = AC |
| 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