題目鏈接

題目

題目描述

一天，小魂正和一個(gè)數(shù)列玩得不亦樂乎。
小魂的數(shù)列一共有n個(gè)元素，第i個(gè)數(shù)為Ai。
他發(fā)現(xiàn)，這個(gè)數(shù)列的一些子序列中的元素是嚴(yán)格遞增的。
他想知道，這個(gè)數(shù)列一共有多少個(gè)長度為K的子序列是嚴(yán)格遞增的。

請你幫幫他，答案對998244353取模。

對于100%的數(shù)據(jù)，1≤ n ≤ 500,000,2≤ K ≤ 10,1≤ Ai ≤ 109。

輸入描述

第一行包含兩個(gè)整數(shù)n,K，表示數(shù)列元素的個(gè)數(shù)和子序列的長度。
第二行包含n個(gè)整數(shù)，表示小魂的數(shù)列。

輸出描述

一行一個(gè)整數(shù)，表示長度為K的嚴(yán)格遞增子序列的個(gè)數(shù)對998244353取模的值。

示例1

輸入

5 3
2 3 3 5 1

輸出

2

說明

兩個(gè)子序列分別是 2 3 3 5 1 和 2 3 3 5 1 。

題解

知識點(diǎn)：樹狀數(shù)組，枚舉，線性dp。

仿照最長上升子序列的狀態(tài)，設(shè) \(f_{i,j}\) 為以第 \(i\) 個(gè)數(shù)結(jié)尾且長度為 \(j\) 的上升子序列個(gè)數(shù)，顯然是 \(O(n^2k)\) 的。其中可以優(yōu)化的步驟是，查找上一個(gè)比自己小的元素。對于最長上升子序列優(yōu)化查找的步驟，通常有三種方法，我們依次考慮是否適合用于這道題的狀態(tài)：

1. 改變狀態(tài)，設(shè) \(f_i\) 為長度為 \(i\) 的上升子序列的最小結(jié)尾數(shù)字，其有單調(diào)遞增的性質(zhì)，因此每次新增數(shù)字，二分查找最后一個(gè)小于自己數(shù)字的位置即可。但是，這個(gè)顯然不適合用來優(yōu)化這道題的狀態(tài)。
2. 優(yōu)化查找，用數(shù)據(jù)結(jié)構(gòu)維護(hù)前綴權(quán)值最大值，即以數(shù)字作為下標(biāo)維護(hù)每個(gè)數(shù)字結(jié)尾的最大長度。這個(gè)方法是可以考慮的，我們將維護(hù)最大長度改為各個(gè)長度的上升子序列個(gè)數(shù)即可。
3. 排序+優(yōu)化查找，將數(shù)字順序改為從小到大輸入，用數(shù)據(jù)結(jié)構(gòu)維護(hù)前綴最大值，即在原本的區(qū)間上維護(hù)每個(gè)位置結(jié)尾的最大長度，輸入順序保證了每次詢問的答案一定都是比自己小的數(shù)字構(gòu)成的答案，都是可以接上的。這個(gè)方法同樣也是可以考慮的，我們將維護(hù)最大長度改為各個(gè)長度的上升子序列個(gè)數(shù)即可。

第二種方法需要先離散化，我們這里使用的是第三種方法，先排序后優(yōu)化查找，復(fù)雜度上是沒有區(qū)別的。

需要注意的是，使用第三種方法從小到大枚舉時(shí)，因?yàn)橐蟮氖巧仙有蛄?，所以相等的?shù)字不能直接更新到數(shù)據(jù)結(jié)構(gòu)中，需要等到所有相等的數(shù)字都查詢完，才能一并更新。第二種方法由于直接維護(hù)權(quán)值關(guān)系，大小可以直接確定，則沒有這種情況。

時(shí)間復(fù)雜度 \(O(nk \log n)\)

空間復(fù)雜度 \(O(nk)\)文章來源地址http://www.zghlxwxcb.cn/news/detail-434571.html

代碼

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int P = 998244353;

template<class T>
class Fenwick {
    int n;
    vector<T> node;

public:
    Fenwick(int _n = 0) { init(_n); }

    void init(int _n) {
        n = _n;
        node.assign(n + 1, T());
    }

    void update(int x, T val) { for (int i = x;i <= n;i += i & -i) node[i] += val; }

    T query(int x) {
        T ans = T();
        for (int i = x;i;i -= i & -i) ans += node[i];
        return ans;
    }
};

int k;
struct T {
    array<int, 17> f = {};
    T &operator+=(const T &x) {
        for (int i = 1;i <= k;i++) (f[i] += x.f[i]) %= P;
        return *this;
    }
};

pair<int, int> a[500007];
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n >> k;
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x;
        a[i] = { x,i };
    }
    sort(a + 1, a + n + 1, [&](auto a, auto b) {return a.first < b.first;});

    int ans = 0;
    Fenwick<T> fw(n);
    vector<pair<int, array<int, 17>>> v;
    for (int i = 1;i <= n;i++) {
        if (a[i].first != a[i - 1].first) {
            for (auto [id, f] : v) fw.update(id, { f });
            v.clear();
        }
        auto res = fw.query(a[i].second).f;
        for (int j = k;j >= 1;j--) res[j] = res[j - 1];
        res[1] = 1;
        (ans += res[k]) %= P;
        v.push_back({ a[i].second,res });
    }
    cout << ans << '\n';
    return 0;
}

到了這里，關(guān)于NC54585 小魂和他的數(shù)列的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！