INCVN - INCSEQ VN

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<cstring>

const int MOD = 5000000, VAL = 1e5 + 1, N = 10000;
int inc[N], bit[VAL+1], n, k, a[N];

void update(int idx, int v) {
    for(; idx <= VAL; idx += idx & -idx)
        bit[idx] = (bit[idx] + v) % MOD;
}

int sum(int idx) {
    long long res = 0;
    for(; idx > 0; idx -= idx & -idx)
        res += bit[idx];
    return res % MOD;
}

int main() {
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; ++i) {
        scanf("%d", a+i);
        ++a[i]; inc[i] = 1;
    }
    for(int l = 2; l <= k; ++l) {
        memset(bit, 0, sizeof bit);
        for(int i = 0; i < n; ++i) {
            update(a[i], inc[i]);
            inc[i] = sum(a[i] - 1);
        }
    }
    long long res = 0;
    for(int i = 0; i < n; ++i) res += inc[i]; 
    printf("%d\n", int(res % MOD));
    return 0;
}

Download