Editorial for Đếm HN

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Đế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;
}