Code : Distinct Subsequences

#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

using mint = modint1000000007;

void solve(string &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<mint>> dp(n + 1, vector<mint>(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;
        if (parent[i] == -1) {
            ndp[1][i] = 1;
        }

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

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

    mint ans = 0;
    for (int len = 1; len <= n; len++) {
        cout << res[len].val() << " ";
        ans += res[len];
    }
    cout << "\n";
    cout << ans.val() << "\n";
}

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

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        string str;
        cin >> str;
        solve(str);
    }
}

#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

using mint = modint1000000007;

void solve(string &str) {
    int n = str.size();

    vector<vector<mint>> dp(n + 1, vector<mint>(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++) {
            mint sum = 0;
            for (int j = 0; j < 26; j++) {
                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<mint> cnt(n + 1, 0);
    // Empty subsequence.
    cnt[0] = 1;
    for (int len = 0; len <= n; len++) {
        for (int j = 0; j < 26; j++) {
            cnt[len] += dp[len][j];
        }
    }

    mint ans = 0;
    for (int len = 1; len <= n; len++) {
        cout << cnt[len].val() << " ";
        ans += cnt[len];
    }
    cout << "\n";
    cout << ans.val() << "\n";
}

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

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        string str;
        cin >> str;
        solve(str);
    }
}

#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

using mint = modint1000000007;

void solve(string &str) {
    // dp[ch] is the number of distinct subsequences ending at character ch.
    vector<mint> dp(26);

    for (char ch : str) {
        mint sum = 0;
        for (int i = 0; i < 26; i++) {
            sum += dp[i];
        }

        // We discard all subsequences ending at last_occ[ch]
        // Hence, you don't see a +=
        dp[ch - 'a'] = 1 + sum;
    }

    mint ans = 0;
    for (int i = 0; i < 26; i++) {
        cout << dp[i].val() << " ";
        ans += dp[i];
    }
    cout << "\n";
    cout << ans.val() << "\n";
}

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

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        string str;
        cin >> str;
        solve(str);
    }
}

#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

using mint = modint1000000007;

void solve(string &str) {
    // dp[ch] is the number of subsequences ending at character ch.
    vector<mint> dp(26);

    for (char ch : str) {
        mint sum = 0;
        for (int i = 0; i < 26; i++) {
            sum += dp[i];
        }

        dp[ch - 'a'] += 1 + sum;
    }

    mint ans = 0;
    for (int i = 0; i < 26; i++) {
        cout << dp[i].val() << " ";
        ans += dp[i];
    }
    cout << "\n";
    cout << ans.val() << "\n";
}

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

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        string str;
        cin >> str;
        solve(str);
    }
}