Dãy con phân biệt II trong C++

Cho chuỗi S, đếm số dãy con phân biệt (không nhất thiết liên tiếp). Kết quả modulo 10^9+7.

Ví dụ: "bab" → 6 (a, b, ba, ab, bb, abb).

Giải thuật

1. DP: dp[c] = số dãy con kết thúc bằng ký tự c.
2. Duyệt từng ký tự x trong S:
   • added = (res + 1) - dp[x] (số dãy con mới kết thúc bằng x).
   • Cập nhật dp[x] += added, res += added.
3. Sử dụng các hàm add, sub, mul modulo 1e9+7.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli MOD = 1e9 + 7;
class Solution {
public:
    lli add(lli a, lli b){ return ( (a % MOD) + (b % MOD) ) % MOD; }
    lli sub(lli a, lli b){ return ( ( (a % MOD) - (b % MOD) ) + MOD ) % MOD; }
    lli mul(lli a, lli b){ return ( (a % MOD) * (b % MOD) ) % MOD; }
    int distinctSubseqII(string s) {
        int n = s.size();
        vector<lli> dp(26);
        int res = 0;
        s = " " + s;
        for(lli i = 1; i <= n; i++){
            char x = s[i];
            int added = sub(add(res, 1), dp[x - 'a']);
            dp[x - 'a'] = add(dp[x - 'a'], added);
            res = add(res, added);
        }
        return res;
    }
};
int main(){
    Solution ob;
    cout << (ob.distinctSubseqII("bab"));
}

Đầu vào

"bab"

Đầu ra

6