1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime>10 #include <list>11 #include <set>12 #include <map>13 using namespace std;14 typedef long long LL;15 typedef pair <int, int> P;16 const int N = 1e3 + 5;17 LL dp[N][N], mod = 1e9 + 7;18 int a[N], b[N], m, n;19 LL bit[N][N];20 21 void add(int pos, int i, int val) { //上升子序列长度为pos 22     for( ; i <= n; i += (i&-i))23         bit[pos][i] = (bit[pos][i] + val) % mod;24 }25 26 LL sum(int pos, int i) {27     LL s = 0;28     for( ; i >= 1; i -= (i&-i))29         s = (s + bit[pos][i]) % mod;30     return s;31 }32 33 int main()34 {35     int t;36     scanf("%d", &t);37     for(int ca = 1; ca <= t; ++ca) {38         scanf("%d %d", &n, &m);39         for(int i = 1; i <= n; ++i) {40             scanf("%d", a + i);41             b[i] = a[i];42         }43         sort(b + 1, b + n + 1);44         for(int i = 1; i <= n; ++i) {45             a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b; //离散化46         }47         memset(dp, 0, sizeof(dp));48         memset(bit, 0, sizeof(bit));49         dp[1][1] = 1;50         add(1, a[1], 1);51         for(int i = 2; i <= n; ++i) {52             dp[i][1] = 1;53             for(int k = max(m - (n - i), 1); k <= min(i, m); ++k) { //这边可以优化一下54                 dp[i][k] = (dp[i][k] + sum(k - 1, a[i] - 1)) % mod; //比a[i]小且上升子序列长度为k-155                 add(k, a[i], dp[i][k]);56             }57         }58         LL res = 0;59         for(int i = 1; i <= n; ++i) {60             res = (res + dp[i][m]) % mod;61         }62         printf("Case #%d: %lld\n", ca, res);63     }64     return 0; 65 }