题意：
求n个数中长度为m的上升子序列的个数
dpij表示到达i位置，长度为j的方案数目！
dp[i][j] = sum( dp[k][j-1], iff a[k] < a[i], 0<=k<i)。树状数组优化dp，对每一个长度都用树状数组记录对应位置的方案数！
这道题主要是让我T的刻骨铭心，好几处位置，一个是%mod，要判断大于了再余!!
一个是m，有可能n很大，m很小，如果每次都把所有的长度都更新必然会造成浪费，因此会T！
还有就是离散化后的上限值，这个倒是没有什么本质上的影响，但也会差400多ms，毕竟是log的级别！
这几点哪一点写挫都有可能导致差那么一点就T掉了！
还有写的时候应该注意赋初值和状态更新的时候是否应该减一，省的浪费时间调！
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e3+10;
const int mod=1e9+7;
int t,n,mm;
int dp[maxn][maxn];int c[maxn][maxn];int a[maxn];int nn;
int lowbit(int x){ return x & (-x);}
void update(int j,int x,int num)
{
while (x < nn)
{
c[j][x] = (c[j][x]+num);if(c[j][x]>=mod) c[j][x]%=mod;
x += lowbit(x);
}
}
int getsum(int j,int x)
{
int sum = 0;
while (x > 0)
{
sum = (sum+c[j][x]);if(sum>=mod) sum%=mod;
x -= lowbit(x);
}
return sum;
}
int main(){
cin>>t;int count=1;
while(t--){
set<int>s;map<int ,int>m;memset(dp,0,sizeof(dp));
memset(c,0,sizeof(c));
scanf("%d%d",&n,&mm);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);s.insert(a[i]);
}
nn =1;
for(auto u:s){
m[u]=nn++;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=mm;j++){
if(j==1) dp[i][j]=1;
dp[i][j]=(dp[i][j]+getsum(j-1,m[a[i]]-1));
if(dp[i][j]>=mod) dp[i][j]%=mod;
update(j,m[a[i]],dp[i][j]);
//cout<<"i= "<<i<<" j="<<j<<" "<<dp[i][j]<<endl;
}
}
int ans=0;
for(int i=1;i<=n;i++){
ans=(ans+dp[i][mm]);
if(ans>=mod) ans%=mod;
}
printf("Case #%d: ",count++);
printf("%d\n",ans);
}
}