ACM学习历程—UESTC 1217 The Battle of Chibi（递推 && 树状数组）(2015CCPC C)

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <string>
#define LL long long
#define MOD 1000000007

using namespace std;

const int maxN = 1005;
int n, m;
struct node
{
    int v;
    int id;
}a[maxN];

bool cmp(node x, node y)
{
    if (x.v != y.v) return x.v < y.v;
    else return x.id > y.id;
}

LL d[maxN][maxN];

int lowbit(int x)
{
    return x&(-x);
}

void add(int len, int id, LL pls)
{
    while(id <= maxN)//id最大是maxN
    {
        d[len][id] += pls;
        d[len][id] %= MOD;
        id += lowbit(id);
    }
}

LL sum(int len, int to)
{
    LL s = 0;
    while(to > 0)
    {
        s = (s+d[len][to])%MOD;
        to -= lowbit(to);
    }
    return s;
}

void input()
{
    scanf("%d%d", &n, &m);
    int k;
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &k);
        a[i].id = i+1;
        a[i].v = k;
    }
    sort(a, a+n, cmp);
    memset(d, 0, sizeof(d));
}

void work()
{
    LL k;
    for (int i = 0; i < n; ++i)
    {
        add(1, a[i].id, 1);
        for (int j = 2; j <= m; ++j)
        {
            k = sum(j-1, a[i].id-1);
            if (!k) break;
            add(j, a[i].id, k);
        }
    }
    printf("%lld\n", sum(m, n));
}

int main()
{
    //freopen("test.in", "r", stdin);
    int T;
    scanf("%d", &T);
    for (int times = 1; times <= T; ++times)
    {
        printf("Case #%d: ", times);
        input();
        work();
    }
    return 0;
}