赤壁之战

AcWing-297-赤壁之战

分析

见《进阶指南》第312页。

实现

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1010, M = 1e9 + 7;
int n, m;
int a[N];
int b, nums[N];
int c[N];
int f[N][N];

void discrete () {
    for (int i = 1; i <= n; ++ i) nums[i] = a[i];
    sort(nums + 1, nums + n + 1);
    b = unique(nums + 1, nums + n + 1) - (nums + 1);
}
int query (int x) {
    return lower_bound(nums + 1, nums + b + 1, x) - nums;
}
int lowbit (int x) {
    return x & -x;
}
void modify (int idx, int val) {
    while (idx <= b) {
        c[idx] = (c[idx] + val) % M;
        idx += lowbit(idx);
    }
}
int sum (int idx) {
    int res = 0;
    while (idx >= 1) {
        res = (res + c[idx]) % M;
        idx -= lowbit(idx);
    }
    return res;
}

int main () {
    int _;
    scanf("%d", &_);
    for (int T = 1; T <= _; ++ T) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);

        discrete();
        for (int i = 1; i <= n; ++ i) a[i] = query(a[i]); 

        for (int i = 1; i <= n; ++ i) f[i][1] = 1;
        for (int j = 2; j <= m; ++ j) {
            memset(c, 0, sizeof(c));
            for (int i = 1; i <= n; ++ i) {
                f[i][j] = sum(a[i] - 1);
                modify(a[i], f[i][j - 1]);
            }
        }
        int res = 0;
        for (int i = 1; i <= n; ++ i)
            res = (res + f[i][m]) % M;
        printf("Case #%d: %d\n", T, res);
    }
    return 0;
}