题目描述

blablabla

样例

blablabla

算法1

(树状数组) $O(n \times m \times log_2(n))$

暴力拼接, 对于a[j]

寻找 a[i] < a[j] && i < j

直接 $\sum_{len=2}^j sum[j][len] += sum[i][len - 1]$

对于长度为一的子数组, 直接 sum[j][1] = 1;

用树状数组维护 sum即可

时间复杂度

参考文献

C++ 代码

int c[N][N], a[N];

void add(int x, int k, int t) { for (; x <= n; x += -x & x) c[t][x] = (c[t][x] + k) % mod; }

int ask(int x, int t) {int ans = 0; for (; x; x -= -x & x) ans = (ans + c[t][x]) % mod; return ans; }

int main() {
    IOS;
    for (cin >> _; _; --_) {
        cin >> n >> m; VI g;
        rep (i, 1, n) cin >> a[i], g.pb(a[i]);
        sort(all(g)); g.erase(unique(all(g)), g.end());
        per (i, g.size(), 1) per (j, g.size(), 1) c[i][j] = 0;
        rep (i, 1, n) {
            a[i] = lower_bound(all(g), a[i]) - g.begin() + 1;
            add(a[i], 1, 1);
            rep (j, 2, m) add(a[i], ask(a[i] - 1, j - 1), j);
        }
        cout << "Case #" << ++cas << ": " << ask(g.size(), m) << '\n';
    }
    return 0;
}