Chef and the Number Sequence
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Chef has a sequence A consisting of N integers each lying between 1 and K, both inclusive. Now he wants to construct another sequence B of the same length also containing integers between 1 and K (again, both inclusive). Find out in how many ways he can construct the sequence B, such that the length of Longest Common Subsequence (LCS) of A and B is exactly L. As the answer could be large, print it modulo 109 + 7.
The first line of the input contains T denoting the number of test cases. Each test case contains two lines:
- The first line of each test case contains three space separated integers N, K, and L.
- The second line contains N space separated integers A1, A2, ... AN.
OutputFor each test case output the number of ways to construct B as described above. Output the result modulo 109 + 7.
- 1 ≤ T ≤ 10
- 1 ≤ N,K ≤ 16
- 1 ≤ L ≤ N
- The sequence A consists of integers between 1 and K (both inclusive).
Input: 2 2 2 1 1 2 3 3 2 1 2 2 Output: 3 11
First Example : There are total three possible valid sequences B : [1, 1], [2, 2] and [2, 1]. LCS of these sequences with sequence A is equal to 1. Note that [1, 2] is not a valid sequence as LCS of this and sequence A is equal to 2.
Second Example: The 11 ways are: [1, 1, 2], [1, 2, 1], [1, 2, 3], [1, 3, 2], [2, 1, 2], [2, 2, 1], [2, 2, 2], [2, 2, 3], [2, 3, 2], [3, 1, 2], [3, 2, 2].
NoteTwo sequences of B are considered different if there is at least one position which contains different numbers in the sequences.
|Tags||cook61, dp+bitmask, medium, rustinpiece|
|Time Limit:||4 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.