Hướng dẫn giải của Đếm HN

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Đếm HN

  • Subtask 2: ~K \leq 10^3~

    • Duy trì một biến ~cnt_H~ để đếm số kí tự H đã được duyệt qua.
    • Với mỗi kí tự N trong xâu ~S~, ghép kí tự đó với tất cả các kí tự H ở trước đó.

  • Subtask 4:

    • Xâu ~S~ có dạng ~XXX..X~, tạm gọi các phần xâu ~X~ liên tiếp là một block.
    • Có hai trường hợp xảy ra:
    • Ký tự H và N cùng trong một block: Dùng phương pháp của subtask 2 để giải quyết.
    • Ký tự H và N ở khác block: Gọi số kí tự H và N trong xâu ~X~ lần lượt là ~cnt_H~ và ~cnt_N~. Số cách chọn xâu con HN cho trường hợp này là: ~\frac{k(k - 1)}{2} \times cnt_H \times cnt_N~.

  • Code tham khảo

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

string x;
long long k;

int main(){
    cin.tie(0)->sync_with_stdio(0);
    freopen("DEMHN.INP", "r", stdin);
    freopen("DEMHN.OUT", "w", stdout);

    cin >> x >> k;

    long long cntH = 0, cntN = 0, ans = 0;
    for (int i = 0; i < x.size(); i++){
        if(x[i] == 'H') cntH++;
        else if(x[i] == 'N'){
            cntN++;
            ans = (ans + cntH) % MOD;
        }
    }

    ans = (ans * k) % MOD;
    ans = (ans + ((cntH * cntN) % MOD) * ((k * (k - 1)) / 2 % MOD)) % MOD;
    cout << ans;
    return 0;
}