权值树状数组记录上一层信息

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1005,mod = 1e9+7;
int T,n,m,t[N],a[N],p[N];
LL f[N][N];
int lowbit(int x){ return x & -x;}
int sum(int x)
{
    int s = 0;
    while(x)
    {
        s = (s+t[x])%mod;
        x -= lowbit(x);
    }
    return s;
}
void add(int x,int d)
{
    while(x <= n)
    {
        t[x] = (t[x] + d)%mod;
        x += lowbit(x);
    }
}
int main()
{
    cin>>T;
    for(int now = 1;now<=T;now++)
    {
        cin>>n>>m;
        memset(f,0,sizeof f);
        //f[i][j]以第j个数结尾，当前长度为i的序列的方案数
        //f[1][i] = 1; f[i][j] = ∑f[i-1][k](k < i && a[k] < a[i])
        for(int i = 1;i<=n;i++)
        {
            cin>>a[i];
            p[i] = a[i];
            f[1][i] = 1;
        }
        sort(p+1,p+n+1);
        int cnt = unique(p+1,p+n+1)-p-1;
        for(int i = 1;i<=n;i++)
            a[i] = lower_bound(p+1,p+cnt+1,a[i])-p;
        for(int i = 2;i<=m;i++)
        {
            memset(t,0,sizeof t);
            for(int j = 1;j<=n;j++)
            {
                f[i][j] = sum(a[j]-1);
                add(a[j],f[i-1][j]);
            }
        }
        LL ans = 0;
        for(int i = 1;i<=n;i++) ans = (ans+f[m][i])%mod;
        printf("Case #%d: %d\n",now,ans);
    }
    return 0;
}