Code : Subsequences (hard version)

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

const long long lim = 1e12;

void add(long long &a, long long delta) {
    a += delta;
    a = min(a, lim);
}

long long solve(string &str, long long k) {
    int n = str.size();
    vector<int> prev(n, -1);

    map<char, int> last_occ;
    for (int i = 0; i < n; i++) {
        if (last_occ.find(str[i]) != last_occ.end()) {
            prev[i] = last_occ[str[i]];
        }
        last_occ[str[i]] = i;
    }

    vector<vector<long long>> dp(n + 1, vector<long long>(n, 0));
    // dp[len][j] is the number of unique subsequences of len 'len' that ends
    // at index j.

    for (int i = 0; i < n; i++) {
        auto ndp = dp;
        int parent = prev[i];
        if (parent == -1) {
            ndp[1][i] = 1;
        }

        for (int len = 0; len < n; len++) {
            for (int j = 0; j < n; j++) {
                if (parent > j) {
                    continue;
                }
                add(ndp[len + 1][i], dp[len][j]);
            }
        }
        swap(ndp, dp);
    }

    // cnt[len] is the number of unique subsequences of length len.
    vector<long long> cnt(n + 1, 0);
    // Empty subsequence.
    cnt[0] = 1;
    for (int len = 0; len <= n; len++) {
        for (int j = 0; j < n; j++) {
            add(cnt[len], dp[len][j]);
        }
    }

    long long cost = 0;
    for (int len = n; len >= 0; len--) {
        if (k >= cnt[len]) {
            k -= cnt[len];
            cost += cnt[len] * (n - len);
        } else {
            cost += k * (n - len);
            k = 0;
        }
    }
    if (k == 0) {
        return cost;
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    long long k;
    cin >> k;
    string str;
    cin >> str;
    cout << solve(str, k) << "\n";
}

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

const long long lim = 1e12;

void add(long long &a, long long delta) {
    a += delta;
    a = min(a, lim);
}

long long solve(string &str, long long k) {
    int n = str.size();

    vector<vector<long long>> dp(n + 1, vector<long long>(26, 0));
    // dp[len][ch] is the number of unique subsequences of len 'len' that ends
    // at character 'ch'.

    for (char ch : str) {
        auto ndp = dp;
        for (int len = 0; len < n; len++) {
            long long sum = 0;
            for (int j = 0; j < 26; j++) {
                add(sum, dp[len][j]);
            }
            ndp[len + 1][ch - 'a'] = sum;
        }
        ndp[1][ch - 'a'] = 1;
        swap(ndp, dp);
    }

    // cnt[len] is the number of unique subsequences of length len.
    vector<long long> cnt(n + 1, 0);
    // Empty subsequence.
    cnt[0] = 1;
    for (int len = 0; len <= n; len++) {
        for (int j = 0; j < 26; j++) {
            add(cnt[len], dp[len][j]);
        }
    }

    long long cost = 0;
    for (int len = n; len >= 0; len--) {
        if (k >= cnt[len]) {
            k -= cnt[len];
            cost += cnt[len] * (n - len);
        } else {
            cost += k * (n - len);
            k = 0;
        }
    }
    if (k == 0) {
        return cost;
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    long long k;
    cin >> k;
    string str;
    cin >> str;
    cout << solve(str, k) << "\n";
}

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

long long solve(string &str, long long k) {
    // Switch to one based indexing.
    str = "$" + str;
    int n = str.size();
    vector<int> parent(n, -1);

    map<char, int> last_occ;
    for (int i = 0; i < n; i++) {
        if (last_occ.find(str[i]) != last_occ.end()) {
            parent[i] = last_occ[str[i]];
        }
        last_occ[str[i]] = i;
    }

    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));
    // dp[i][j] is the number of distinct subsequences of length j of the
    // prefix [1 ... i]

    dp[0][0] = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= n; j++) {
            // Ignore the current element.
            dp[i][j] = dp[i - 1][j];

            if (j == 0) {
                continue;
            }
            if (dp[i][j] >= 1e18) {
                continue;
            }

            // Take the last element.
            dp[i][j] += dp[i - 1][j - 1];

            // Fix the double counting.
            if (parent[i] > 0) {
                dp[i][j] -= dp[parent[i] - 1][j - 1];
            }
        }
    }

    // cnt[len] is the number of unique subsequences of length len.
    vector<long long> cnt(n + 1, 0);
    for (int len = 0; len <= n; len++) {
        cnt[len] = dp[n - 1][len];
    }

    // Switch back to zero based indexing.
    n--;

    long long cost = 0;
    for (int len = n; len >= 0; len--) {
        if (k >= cnt[len]) {
            k -= cnt[len];
            cost += cnt[len] * (n - len);
        } else {
            cost += k * (n - len);
            k = 0;
        }
    }
    if (k == 0) {
        return cost;
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    long long k;
    cin >> k;
    string str;
    cin >> str;
    cout << solve(str, k) << "\n";
}