Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const long long mod = 1e9;
- int n, k;
- vector<int> a;
- vector<vector<long long>> tree;
- long long res;
- void update(int level, int v, int tl, int tr, int pos, long long x) {
- if (tl == tr) {
- tree[level][v] += x;
- } else {
- int tm = (tl + tr) / 2;
- if (pos <= tm) {
- update(level, v * 2, tl, tm, pos, x);
- } else {
- update(level, v * 2 + 1, tm + 1, tr, pos, x);
- }
- tree[level][v] = tree[level][v * 2] + tree[level][v * 2 + 1];
- }
- tree[level][v] %= mod;
- }
- long long sum(int level, int v, int tl, int tr, int l, int r) {
- if (l > r) {
- return 0;
- }
- if (tl == l && r == tr) {
- return tree[level][v];
- }
- int tm = (tl + tr) / 2;
- return (sum(level, v * 2, tl, tm, l, min(r, tm)) + sum(level, v * 2 + 1, tm + 1, tr, max(tm + 1, l), r)) % mod;
- }
- int main() {
- cin >> n >> k;
- a.resize(n, 0);
- for (int i = 0; i < n; ++i) {
- cin >> a[i];
- }
- tree.resize(k, vector<long long> (4 * n + 1, 0));
- for (int i = 0; i < n; ++i) {
- long long val = 1;
- for (int j = 0; j + 1 < k; ++j) {
- long long cur = sum(j, 1, 1, n, a[i] + 1, n);
- update(j, 1, 1, n, a[i], +val);
- val = cur;
- if (j == k - 2) {
- res += cur;
- res %= mod;
- }
- }
- }
- cout << res;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
