基本思路：
- 权值树状数组.
状态设计：
- f[子序列长度][当前位数]（严格递增子序列数量）.
易错点：
- 初始化时需要设置f[0][0]=1.
- 每个独立的数字都只会影响到比它更大的数字.
- 预处理时的sort保证了整个算法的正确性.
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int MAXN=2e3,MOD=1e9+7;
int lowbit(int x){
return x&-x;
}
int c[MAXN];
ll ask(int x){
ll ans=0;
while(x){
ans+=c[x];
ans=ans%MOD;
x-=lowbit(x);
}
return ans;
}
void add(int x,int value){
while(x<=MAXN){
c[x]+=value;
c[x]=c[x]%MOD;
x+=lowbit(x);
}
}
int a[MAXN],b[MAXN];
int f[MAXN][MAXN];
int main(){
int T;
scanf("%d",&T);
int caseCnt=0;
while(T--){
caseCnt++;
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
memcpy(b,a,sizeof(b));
sort(b+1,b+1+n);
for(int i=1;i<=n;i++){
a[i]=lower_bound(b+1,b+n+1,a[i])-(b-1);
}
f[0][0]=1;
for(int i=1;i<=m;i++){
memset(c,0,sizeof(c));
if(i==1)add(1,f[i-1][0]);
for(int j=1;j<=n;j++){
f[i][j]=ask(a[j]-1);
add(a[j],f[i-1][j]);
}
}
int ans=0;
for(int i=1;i<=n;i++){
ans+=f[m][i];
ans=ans%MOD;
}
printf("Case #%d: %d
",caseCnt,ans);
}
return 0;
}