Hiểu bài toán

Bài toán yêu cầu tìm số lượng xâu ban đầu có thể tạo ra xâu lỗi S已知. Khi một phím được nhấn, bàn phím hỏng có thể tạo ra một hoặc nhiều ký tự liên tiếp của cùng một ký tự đó. Ví dụ, nếu nhấn 'a', có thể tạo ra 'a', 'aa', 'aaa', ... Tuy nhiên, các ký tự khác nhau trong xâu ban đầu phải được gõ theo thứ tự, và các đoạn ký tự liên tiếp trong xâu lỗi S (ví dụ 'ttt') có thể đến từ một lần nhấn 't' (tạo ra 'ttt') hoặc nhiều lần nhấn 't' liên tiếp (ví dụ 't' + 'tt'). Do đó, với mỗi đoạn chạy (run-length) gồm $k$ ký tự giống nhau trong S, số cách để tạo ra đoạn này từ các lần nhấn phím tương ứng chính là số cách phân tích số $k$ thành tổng các số nguyên dương (composition). Tuy nhiên, các giải pháp accepted lại cho kết quả là tích của độ dài các đoạn chạy. Điều này có nghĩa là cách hiểu vấn đề thực tế là: với mỗi đoạn gồm $k$ ký tự liên tiếp giống nhau trong S, có $k$ cách chọn cách chia (tức là số lượng 'móc' giữa các lần nhấn, ví dụ với $k=3$: (1,2), (2,1) là 2 cách, cộng với (3) là 1 cách? Không, thực ra là $k$ cách). Phân tích kỹ: Với $k$ ký tự 'a' liên tiếp, ta cần chia chúng thành $m$ khối (mỗi khối tương ứng 1 lần nhấn). Nếu chia thành $m$ khối, có $?inom{k-1}{m-1}$ cách. Tổng cộng có $2^{k-1}$ cách. Tuy nhiên, các giải pháp accepted tính kết quả là tích của $k$ (với $k$ là độ dài đoạn chạy). Ví dụ 'tyypppinng' có các đoạn 'y':2, 'p':3, 'n':2. Tích là $2 imes 3 imes 2 = 12$. Điều này cho thấy bài toán có thể được hiểu theo cách khác hoặc các giải pháp accepted là sai logic nhưng đúng testcases. Tuy nhiên, dựa trên các giải pháp accepted, bài toán yêu cầu tính tích của độ dài các đoạn chạy liên tiếp của các ký tự giống nhau trong S.

Các cách tiếp cận

Cách Duyệt chuỗi và tính toán

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    const long long MOD = 1000000007LL;
    string s;
    if (!(cin >> s)) return 0;

    long long result = 1;
    int n = (int)s.size();
    int i = 0;
    while (i < n) {
        int j = i + 1;
        while (j < n && s[j] == s[i]) j++;
        int runLength = j - i;
        result = (result * runLength) % MOD;
        i = j;
    }

    cout << result;
    return 0;
}

• Time Complexity: O(|S|)
• Space Complexity: O(1)

Thuật toán duyệt qua xâu S từ đầu đến cuối. Với mỗi ký tự bắt đầu một đoạn chạy mới, nó đếm số lượng ký tự liên tiếp giống nhau (run-length). Sau đó, nó nhân dồn kết quả vào biến result với modulo $10^9+7$. Ví dụ, với xâu 'tyypppinng':

• 't': độ dài 1, nhân 1 (không thay đổi).
• 'y': độ dài 2, nhân 2 -> result = 2.
• 'p': độ dài 3, nhân 3 -> result = 6.
• 'i': độ dài 1, nhân 1 -> result = 6.
• 'n': độ dài 2, nhân 2 -> result = 12.
• 'g': độ dài 1, nhân 1 -> result = 12. Kết quả là 12, khớp với sample.

Cách Cải tiến về vòng lặp

#include <bits/stdc++.h>
#define el '\n'
#define ll long long
#define N 1000000
#define MOD 1000000007
using namespace std;
string s;
ll T;
vector<ll> v;
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);cout.tie(NULL);
            cin>>s;
            ll ans=1; ll res=1;
            for(ll i=0;i<s.size();i++){
                 if(s[i]==s[i+1]) res++;
                 else {
                   v.push_back(res);res=1;
                 }
            }
            for(ll i=0;i<v.size();i++){
                ans=(ans*v[i])%MOD;
            }
            cout << ans << el;
            return 0;
}

• Time Complexity: O(|S|)
• Space Complexity: O(|S|)

Cách tiếp cận này sử dụng một vector phụ để lưu trữ độ dài của các đoạn chạy. Nó duyệt qua xâu S, đếm độ dài đoạn chạy hiện tại. Khi gặp ký tự khác hoặc kết thúc xâu, nó đẩy độ dài đó vào vector và reset biến đếm. Sau đó, nó duyệt vector để nhân các giá trị lại. Cách này về cơ bản giống cách 1 nhưng dùng nhiều bộ nhớ hơn do lưu các độ dài vào vector thay vì nhân trực tiếp.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể được quy về bài toán đếm số cách phân tích độ dài các đoạn chạy liên tiếp của các ký tự giống nhau trong xâu lỗi. Tuy nhiên, các giải pháp accepted cho thấy quy luật đơn giản là tích các độ dài đoạn chạy.
• Mỗi đoạn gồm $k$ ký tự liên tiếp giống nhau contributes một hệ số là $k$ vào kết quả cuối cùng.

Lỗi thường gặp

• Quên chia kết quả cho modulo $10^9+7$ sau mỗi phép nhân có thể dẫn đến tràn số (overflow) với các xâu dài.
• Xử lý sai trường hợp cuối chuỗi khi duyệt (ví dụ vòng lặp i < s.size() - 1 nhưng không xử lý ký tự cuối cùng).