TPINCD - Dãy con tăng

Tác giả: ladpro98

Ngôn ngữ: C++

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int K = 55;
const int N = 10005;
const int MOD = 15111992;
using namespace std;

struct fenwickTree {
    int bit[N];
    void Upd(int i, int x) {
        for(i++; i < N; i += i & -i) {
            bit[i] += x; 
            if (bit[i] >= MOD) bit[i] -= MOD;
        }
    }
    int Get(int i) {
        int s = 0; 
        for(i++; i; i -= i & -i) {
            s += bit[i];
            if (s >= MOD) s -= MOD;
        }
        return s;
    }
} BIT[K];
int F[K][N], a[N], was[N];
II b[N];
int n, k;

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    REP(i, 1, n) {cin >> a[i]; b[i] = MP(a[i], i);}
    sort(b + 1, b + 1 + n);
    int d = 0;
    REP(i, 1, n) {
        if (i == 1 || b[i].X != b[i - 1].X) d++;
        a[b[i].Y] = d;
    }
    BIT[0].Upd(0, 1);

    REP(j, 1, k) {
        REP(i, 1, d) was[i] = 0;
        REP(i, 1, n) {
            F[j][i] = BIT[j - 1].Get(a[i] - 1);
            BIT[j - 1].Upd(a[i], (F[j - 1][i] - was[a[i]] + MOD) % MOD);
            was[a[i]] = F[j - 1][i];
        }
    }
    REP(i, 1, d) was[i] = 0;
    int ans = 0;
    REPD(i, n, 1)
    if (was[a[i]] == 0) {
        ans += F[k][i];
        if (ans >= MOD) ans -= MOD;
        was[a[i]] = 1;
    }
    cout << ans;
    return 0;
}

Download