2066 . Counting Arrays
TopCoder
Tags
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$。
Output Format
對於每筆測資輸出一行包含一個非負整數，代表滿足條件的嚴格遞增子序列數量除以$2^ {61}-1$的餘數。
Sample Input 1
2
5 1
1 1 1 1 1
5 2
1 2 3 4 2
5 1
1 1 1 1 1
5 2
1 2 3 4 2
Sample Output 1
5
12
12
Hints
Problem Source
Problem set by Yihda Yol
建國中學107學年度校隊選拔：複試pB
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 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 |