TopCoder

Thumb output jddoia
$\huge 南ことり$
今天也要輸贏!?

User's AC Ratio

75.0% (12/16)

Submission's AC Ratio

29.5% (23/78)

Description

你也許有聽過「最長嚴格遞增子序列(LIS)」問題,那你有聽過「嚴格遞增子序列計數」問題嗎?

這個問題可以簡單的描述如下:給定一個長度為$N$的正整數序列$a_0,a_1,\cdots,a_{N-1}$,請求出這個序列有幾個相異且長度介於$1$到$K$之間的嚴格遞增子序列。
具體來說,請計算出有幾個相異的序列$b_0,b_1,\cdots,b_{M-1}$ 滿足 $1\leq M\leq K, 0\leq b_0<b_1<\cdots<b_{M-1}<N$ 且 $a_{b_0}<a_{b_1}<\cdots<a_{b_{M-1}}$。

因為答案可能很大,所以求出答案除以$2^ {61}-1$的餘數就可以了。

Input Format

本題有多筆測資。
第一行有一個正整數$T$,代表測資筆數。
每筆測資第一行有兩個以空白隔開的正整數$N,K$;第二行有$N$個以空白隔開的正整數$a_0,a_1,\cdots,a_{N-1}$。

對於所有測資, $T\leq 8, N\leq10^ 5, K\leq 70, a_i\leq 10^ 9$。

子任務(測資) 額外限制 分數
1 (0) $K=1$ 3
2 (0~1) $K\leq 2$ 17
3 (0~2) $K\leq 3$ 10
4 (3) $a_i\leq 2$ 6
5 (3~4) $a_i\leq 100$ 12
6 (5) $N\leq 20$ 5
7 (5~6) $N \leq 800$ 10
8 (5~7) $N \leq 10^ 4$ 16
9 (0~8) 無額外限制 21

Output Format

對於每筆測資輸出一行包含一個非負整數,代表滿足條件的嚴格遞增子序列數量除以$2^ {61}-1$的餘數。

Sample Input

2
5 1
1 1 1 1 1
5 2
1 2 3 4 2

Sample Output

5
12

Hints

Problem Source

Problem set by Yihda Yol
建國中學107學年度校隊選拔:複試pB

Subtasks

For Testdata: 0 ~ 0, Score: 3
For Testdata: 0 ~ 1, Score: 17
For Testdata: 0 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 6
For Testdata: 3 ~ 4, Score: 12
For Testdata: 5 ~ 5, Score: 5
For Testdata: 5 ~ 6, Score: 10
For Testdata: 5 ~ 7, Score: 16
For Testdata: 0 ~ 8, Score: 21
No. Time Limit (ms) Memory Limit (KiB)
0 2000 262144
1 2000 262144
2 2000 262144
3 7000 262144
4 7000 262144
5 2000 262144
6 5000 262144
7 4500 262144
8 7000 65536